比赛链接:https://codeforces.ml/contest/1742
A题:水题
B题:水题
C题:思维+审题。 大意是给出一个8*8的矩阵,每次操作可以画一行红色或者是一列蓝色,每次绘制可以覆盖之前的颜色。求出最后画的是哪一笔?题目保证给出一个正确解。
这个题WA了9发,导致没时间做F和G题。看着是一个很简单的题,第一眼直接暴力。这是障眼法。
RRRRRRRR RRRRRRRR RRRRRRRR RRRRRRRR RRRRRRRR RRRRRRRR RRRRRRRR BBBBBBBB
我们总能通过这个样例看到一个极端情况,就是B一定不可能画在行上,且红一定不可能画在列上,所以我们不能暴力相等条件,因为RB存在冲突。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void solve() { string a[10]; //cin.ignore(numeric_limits<streamsize>::max(),'\n'); for(int i=0;i<8;i++){ cin>>a[i]; } char c = 'B'; for(int i=0;i<8;i++){ if(a[i] == "RRRRRRRR"){ c = 'R'; break; } } cout<<c<<endl; } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n') //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
D题:给出一组数据,如果两个数互质,产生的值为这两个数之和,求出最大的值,特判1。不存在输出-1。
第一个开的题,上来就有思路,一发AC。
暴力这个题,将是一个n^2的一个复杂度。从单个ai的角度来看,这个数就很小了,只有1000以内,标记数并暴力获得。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } const int nn = 2*1e5+10; int sign[1100]; void solve() { memset(sign,0,sizeof sign); int n; cin>>n; int x; for(int i=1;i<=n;i++){ cin>>x; sign[x] = i; } int maxt = -1; if(sign[1]) maxt = sign[1]+sign[1]; for(int i=1;i<=1000;i++){ for(int j=i+1;j<=1000;j++){ if(sign[i]&&sign[j]&&__gcd(i,j)==1){ maxt = max(maxt,sign[i]+sign[j]); } } } cout<<maxt<<endl; } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n') ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
E题:前缀和+二分。给出一组数据,每组数据代表当前楼梯比之前一个高多少,给出一组数据,每组数据为你可以跨过的高度。求出每个数据能够跨过总数多长的楼梯。
思路:前缀和+map记录每个跨越高度可以到达的总数,不断更新它。二分查找这个值。
code:(代码写拉了,手写二分了。可以一个数组记录前缀和,一个数组记录每个bi能够到达的位置,最后二分查找最后的位置所对应的前缀和即可)
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } map<ll,ll> mp; struct data{ ll tx; ll ts; }; void solve() { mp.clear(); int n,q; cin>>n>>q; ll maxt = 0; ll s = 0; ll x; for(int i=1;i<=n;i++){ cin>>x; s+=x; maxt = max(maxt,x); mp[maxt] = s; } map<ll, ll>::iterator iter; vector<data>ve; ve.push_back({0,0}); iter = mp.begin(); while(iter != mp.end()){ ll key = iter->first; ll val = iter->second; ve.push_back({key,val}); iter++; } ll mx; for(int i=1;i<=q;i++){ cin>>mx; ll l = 0,r = ve.size(); while(l<r){ ll mid = (l+r)>>1; if(ve[mid].tx<=mx) l=mid+1; else if(ve[mid].tx>mx) r=mid-1; } if(l>=ve.size()) cout<<ve[ve.size()-1].ts<<' '; else if(l+1<ve.size()&&mx>=ve[l+1].tx) { cout<<ve[l+1].ts<<' '; } else if(l-1>=0&&mx<ve[l].tx){ cout<<ve[l-1].ts<<' '; } else cout<<ve[l].ts<<' '; } cout<<endl; } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n') ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
F题:由于C题耽误的时间很长,没时间看F题,赛后F第三发过了。大意是给出一个字符串s和t。前缀都是'a',给出两种操作。
给s加上k个新字符串,给t加上k个新字符串。求是否存在s和t的一种排列,使得s的字典序比t小。可以yes不可以no
思路:这个题代码也写拉了,我是开数组分别记录每个s和t中元素出现的数量。正序存储s,倒序存储t。使得贪心最优可能性。
然后开始判断,如果s的字符c小,那么直接ok。如果大,直接no。同样大且数量相同继续看。
同样大且s的少,如果s存在其他no,否则yes。同样大且t的少,如果t存在其他那么no。反复如此。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } ll a[200]; ll b[200]; struct data{ int c; ll cnt; }; // 2a 2b // 11a 3b 3c void solve() { memset(a,0,sizeof a); memset(b,0,sizeof b); a['a'] = 1; b['a'] = 1; int q; cin>>q; int op,x; string s; while(q--){ cin>>op>>x>>s; if(op==1){ for(int i=0;i<s.size();i++) a[s[i]]+=x; }else{ for(int i=0;i<s.size();i++) b[s[i]]+=x; } bool flag = false; vector<data> va; vector<data> vb; for(int i='a';i<='z';i++) { if(a[i]) va.push_back({i,a[i]}); } for(int i='z';i>='a';i--){ if(b[i]) vb.push_back({i,b[i]}); } int mint = min(va.size(),vb.size()); for(int i=0;i<mint;i++){ if(va[i].c<vb[i].c){ flag = true; break; }else if(va[i].c>vb[i].c){ flag = false; break; }else{ if(va[i].cnt>vb[i].cnt){ if(i+1<vb.size()){ flag = true; break; }else{ flag = false; break; } } if(va[i].cnt<vb[i].cnt){ if(i+1<va.size()) { flag = false; break; }else{ flag = true; break; } } } } printf("%s\n",flag?"YES":"NO"); } } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n') ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
G题:读错了!!!或运算读成了异或运算,真服了。大意是给出n个数,定义数组b为n个数的前缀或,求n的一个排列使得前缀或b字典序最大。
或运算如果存在一个1,那么之后都是1.我们只想考虑1是否能带来怎样的效应,找到当前前缀或没有的1的数。最多存在31个这样的情况。剩下随意输出,因为前缀和已经永远满足一个最大。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } struct data{ int x; int s; }; void solve() { int n; cin>>n; vector<int> a(n+1); for(int i=1;i<=n;i++){ cin>>a[i]; } int ors = 0; vector<bool> sign(n+10,false); vector<int> ve; for(int i=1;i<min(n+1,32);i++){ int mx = 0, pos = -1; for(int j=1;j<=n;j++){ if(sign[j]) continue; if((ors|a[j])>mx){ mx = (ors|a[j]); pos = j; } } sign[pos] = true; ors = a[pos]|ors; ve.push_back(a[pos]); } for(int i=0;i<ve.size();i++){ cout<<ve[i]<<' '; } for(int i=1;i<=n;i++){ if(!sign[i]) cout<<a[i]<<' '; } cout<<endl; } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n') ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }