打的很烂的一场 C想了很久 D的贪心没有贪好 赛后一小时补起来了 谁是nc 我是nc!
A. Matching
问有多少种情况能匹配 就计算?的个数 x10x10......
如果第一个是? 那么就是9x10x10...
如果第一个是0 不能有前导0 就输出0
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int f[2]; void solve(){ string s;cin>>s; f[0]=0,f[1]=0; int n=s.length(); int flag=0,res=0,cnt=0; int ans=1; for(int i=0;i<n;i++){ if(s[i]=='?'){ if(flag==0) { res=1; }cnt++;flag=1; f[0]=f[0]*10+9; } else{ flag=1; int k=s[i]-'0'; f[0]=f[0]*10+k; } } for(int i=0;i<cnt;i++){ if(res) ans*=9,res--; else ans*=10; } if(f[0]==0||s[0]=='0') ans=0; cout<<ans<<"\n"; } signed main(){ close; int t;cin>>t; while(t--) solve(); }
B. Sort the Subarray
题目没看清 这个题就是问你 执行一次操作 使第一个数组等于第二个 问选择区间最长的区间
以为可以执行很多次 但是其实只有一次 因此上下不同的数字肯定要丢上去 所以我直接记录第二个数组的非递减长度,如果上下不一样 flag=1 才能取max 如果非递减结束 flag=0 防止后续影响
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int a[MAXN],b[MAXN]; void solve(){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++) cin>>a[i]; int maxs=0,cnt=1,r; int flag=0; for(int i=2;i<=n;i++){ if(a[i]!=b[i]) flag=1; if(a[i]>=a[i-1]) { cnt++; } else{ cnt=1; flag=0; } if(cnt>maxs&& flag){ maxs=cnt; r=i; } } cout<<r-maxs+1<<" "<<r<<"\n"; } signed main(){ // close; int t ;cin>>t; while(t--) solve(); }
C. Tear It Apart
想了很久怎么搞 但实际上打个表就知道怎么搞了。。。
设某个字符char切割后的字符串有至少两个区间(反正取一个区间的必不可能是最优解,消不掉而且最大 不用管) 那么 区间消的次数肯定是以最大的为准
两个区间最大的为1 只需要一次就行
2---2
3---2
4---3
5---3
........
8----4
我们发现 这个最大值都是log2(n)+1
然后就可以直接写了
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ string s; cin>>s; int n=s.length(); int ans=inf; for(char i='a';i<='z';i++){ int cnt=0,maxs=0; for(int j=0;j<n;j++){ if(s[j]==i) cnt=0; else cnt++; maxs=max(cnt,maxs); } ans=min(ans,maxs); } if(ans==0) cout<<0<<"\n"; else{ int k=log2(ans); cout<<k+1<<"\n"; } } signed main(){ int t;cin>>t; while(t--) solve(); }
D. Black Cells
给定很多个不相交的区间 从0开始走 往无限大走,可以执行3个操纵 1-往右走一步 2-按下shift 开始标记路径 3-松开shift 结束标记
只有在给定区间 才能按下/松开shift
这个题的关键在于长度为1的区间 下面给出一个例子方便理解
9 7
1 3 5 7 9 11 13 15 18
1 3 5 7 9 11 13 16 25
我们需要取的是7个 前面1刚好有7个 但是这样显然不是最优解 显然取 15-16,18-22才是最优解
因为在黑色格子后面还能连续的时候 往后走一位只是让总数+1 但是去掉一个前面的1会让总数-2 会赚一个
我的思路就是 枚举每一个区间 当这个区间为结束区间的时候 需要的步数是多少 取最大值即可
显然的 区间长度>=2就必须取上 后面不管怎么样都是赚 就从前往后扫每个区间 如果加上这个区间后的总数(res)>=需要的数(m)
那么我们相当于有res-m的空挡可以用来交换前面的1 此时指针结束的位置就是 r(右端点)-res+m+min(res-m,cnt);
换掉多少个1 就给记录 取区间个数的变量(sum) -2 给剩余可交换的减少这么多
再往后遍历区间 因为1特别多的情况下 可能出现取很多个后面的区间仍然是赚的情况 所以不能break
代码比较乱 如下 中间传vector是之前看错题目 以为区间相交 无视就行orz
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; #define int long long struct node{ int l,r; }a[MAXN]; vector<pair<int,int> > sz; bool bj(node p,node q){ if(p.l!=p.l) return p.l<q.l; else return p.r<q.r; } void solve(){ int n,m;cin>>n>>m; sz.clear(); for(int i=0;i<n;i++){ cin>>a[i].l; } for(int i=0;i<n;i++){ cin>>a[i].r; } sort(a,a+n,bj); // int last=-2; for(int i=0;i<n;i++){ int ll=sz.size(); // if(a[i].l==last+1){ // sz[last-1].second=a[i].r; // last=a[i].r; // } // else { sz.push_back({a[i].l,a[i].r}); // last=a[i].r; // } } int cnt=0,res=0,sum=0,ans=inf; for(auto i:sz){ int l=i.first,r=i.second; if(r-l==0) cnt++;//记录个数 res+=r-l+1;//目前区间的长度和 sum+=2; if(res>=m){ int k=res-m; k=min(k,cnt);int last; last=r-res+m+k;//记录结束点 cnt-=k;//肯定要减去 因为这个区间必须要取(如果这个是1 不影响) 才能往后 sum-=2*(k); ans=min(ans,sum+last); res=m;//防止之后的操作出问题,要变回m 计算下个区间 } } if(ans==inf) ans=-1; cout<<ans<<"\n"; } signed main(){ int t;cin>>t; while(t--) solve(); }
E之后再补 我是菜鸡 写错轻喷 感谢大佬能看完ORZ
- cf-Educational Educational Codeforces Round 147cf-educational educational codeforces round educational codeforces round 147 educational codeforces round rated educational codeforces round 151 construction educational codeforces round educational codeforces round 158 educational codeforces monsters round educational codeforces contest round cf-educational educational codeforces beautiful round