比赛链接:https://codeforc.es/contest/1703
这次比赛做了ABCE四个题,其中D和F题疯狂TLE,我很无语。比赛的难度并不大,最后一题没有看应该是个dp问题,f题是个dp的前置题,有dp的思想在里面。
A题:if else 水题
code:
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { string a; cin>>a; if((a[0]=='y'||a[0]=='Y')&&(a[1]=='e'||a[1]=='E')&&(a[2]=='s'||a[2]=='S')) printf("YES\n"); else printf("NO\n"); } }
B题:大意就是给一个字符串找出出现不同类别的数量然后加上总数就OK了
code:
#include<bits/stdc++.h> using namespace std; int sign[26]; int main() { int t; cin>>t; while(t--) { memset(sign,0,sizeof sign); int n; scanf("%d",&n); string a; cin>>a; for(int i=0;i<a.size();i++) { sign[a[i]-65]=1; } int sum = 0; for(int i=0;i<26;i++) if(sign[i]) sum++; printf("%d\n",sum+a.size()); } }
C题:给出几个数,每个数给出一些操作,然后反向一下。U将数字-1,D+1,这里需要理解题意。然后输出就OK了
code:
#include<bits/stdc++.h> using namespace std; int a[110]; int main() { int t; cin>>t; while(t--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int x; string b; for(int i=1;i<=n;i++) { scanf("%d",&x); cin>>b; // cout<<"!"<<b.size()<<"!"; for(int j=0;j<b.size();j++) { if(b[j]=='D') { a[i]++; if(a[i]==10) a[i]=0; if(a[i]==-1) a[i]=9; } if(b[j]=='U') { a[i]--; if(a[i]==10) a[i]=0; if(a[i]==-1) a[i]=9; } } } for(int i=1;i<=n;i++) printf("%d ",a[i]); printf("\n"); } }
D题:这道题就是我TLE的题,比赛的时候钻牛角尖了,这个题就是给出很多字符串,求每个字符串是否能被其他两个字符串相加所得到。字符串长度“不超过8”。
解决方法:这个题需要注意的点就是长度不超过8。这个数据量很小,所以应该从这里开始分割,这么一看,最多也就只有7种可能。我们可以把每个字符串都放到set里面,这个操作是nlogn,然后我们分割每一个字符去寻找,这里最多也是7*nlogn。正解就是nlogn了。我自己想到n^2logn的那种算法。其实完全可以将其中n用长度来入手。
code:
#include<bits/stdc++.h> using namespace std; const int nn = 1e5+10; string a[nn]; int num[nn]; set<string> se; int main() { int t; cin>>t; while(t--) { memset(num,0,sizeof num); se.clear(); for(int i=0;i<nn;i++) a[i].clear(); int n; scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>a[i]; se.insert(a[i]); } for(int i=1;i<=n;i++) { for(int j=1;j<a[i].size();j++) { if(se.find(a[i].substr(0,j))!=se.end()&&se.find(a[i].substr(j,a[i].size()-j))!=se.end()) { num[i] = 1; break; } } } for(int i=1;i<=n;i++) printf("%d",num[i]); printf("\n"); } }
E题:推导题,有点类似之前做过的黑白块题。大意就是给出一个n*n的矩阵,元素都是0 或 1 ,求我们最少改变多少块元素,可以使得这个矩阵0 90 180 270 360旋转和它本身一致。
解决方法:这个题就是可以从一个元素入手,然后推导出其他三个旋转后的替代点,然后暴力一下这个矩阵,需要改变的元素是4个点中出现次数最少的0或1,可以令4个点相加,这样就是1个数量,那么4-这个数,就是0的数量,然后对比。最后答案除以4。
code:
#include<bits/stdc++.h> using namespace std; string a[110]; int main() { int t; cin>>t; while(t--) { for(int i=0;i<110;i++) a[i].clear(); int n,sum=0; scanf("%d",&n); for(int i=0;i<n;i++) cin>>a[i]; n--; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++)// 0,0 2,0 2,2 0,2 { if(a[i][j]!=a[n-j][i]||a[i][j]!=a[n-i][n-j]||a[i][j]!=a[n-(n-j)][n-i]) { int possum = (a[i][j]+a[n-j][i]+a[n-i][n-j]+a[n-(n-j)][n-i])-48*4; sum+=min(possum,4-possum); } } printf("%d\n",sum/4); } }
F题:这个题是个前缀后缀和二分的题。大意是,给出一组数据,对于一个i<j来说,a[i]<i<a[j]<j,让我们找有多少对这样的数据。
解决方法:另开一个数组,记录这个位置之前有多少已经满足a[i]<i,因为当a[j]>i时,那么i之前所有满足a[i]<i的元素都可以满足。所以可以用前缀和思想解题。
另外一种方法就是二分解决。用一个数组存储满足a[i]<i的数,然后每次遇到一个a[i]<i,我们去对比之前已经存在的满足数据,然后通过a[j]的大小和之前存在的[i]进行一个对比,找到地址后一相减就可以知道之前有多少个数了然后再存储j下标,由于存储的都是下标,所以是有序的可以二分。
前缀code:
#include<bits/stdc++.h> using namespace std; const int nn = 2*1e5 +10; #define ll long long ll v[nn]; int main() { int t; cin>>t; while(t--) { memset(v,0,sizeof v); ll n,k,sum=0; cin>>n; for(ll i=1;i<=n;i++) { cin>>k; v[i] = v[i-1]; if(k<i) v[i]++,sum+=v[k-1]; } cout<<sum<<endl; } }
二分code:
#include <bits/stdc++.h> using namespace std; const int MAX = 200007; const int MOD = 1000000007; void solve() { int n; cin >> n; int a[n + 1]; for (int i = 1; i <= n; i++) { cin >> a[i]; } long long res = 0; vector<int> v; for (int i = 1; i <= n; i++) { if (a[i] >= i) {continue;} res += (long long)(lower_bound(v.begin(), v.end(), a[i]) - v.begin()); v.push_back(i); } cout << res << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} // solve(); }