Codeforces Round #579 (Div. 3)
题意：
给出一个序列，问你是否能构成1-n的环或者n-1的环。
题解：
处理一下序列，取模就行了。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long int a[205]; int main() { int t,n; cin>>t; while(t--) { int flag1 = 0,flag2 = 0; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; a[i] -= 1; } // 3 0 1 2 // 3 0 1 2 for(int i=1;i<n;i++){ if((a[i]+1)%n != a[i+1]%n) flag1 = 1; if((a[i+1]+1)%n != a[i]%n) flag2 = 1; } if(!flag1||!flag2) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
题意：
给出你4*n个木棍，问你是否能组成n个面积相同的矩形。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long int a[404],b[202]; int main() { int t,n; cin>>t; while(t--) { set<int> s; cin>>n; int cnt = 0,flag = 0; for(int i=1;i<=4*n;i++){ scanf("%d",&a[i]); } sort(a+1,a+1+4*n); for(int i=1;i<=4*n;i+=2){ if(a[i] != a[i+1]){ flag = 1; }else{ b[++cnt] = a[i]; } } if(flag){ cout<<"NO"<<endl; continue; } for(int i=1;i<=n;i++) { int k = b[i]*b[2*n-i+1]; s.insert(k); } if(s.size() == 1){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } return 0; }
题意：
给出n个数，让你找出这些数的公因数的个数。
题解：
先算出所有数的最大公因数，然后照这个公因数的因子个数。
代码：#include <bits/stdc++.h> using namespace std; #define ll long long ll a[400005]; int main() { int n; cin>>n; scanf("%lld",&a[1]); ll gcd = a[1]; for(int i=2;i<=n;i++) { scanf("%lld",&a[i]); gcd = __gcd(gcd,a[i]); } ll ans = 0; for(ll i=1;i*i<=gcd;i++) { if(gcd%i == 0){ ans++; if(i*i != gcd) ans++; } } cout<<ans<<endl; return 0; }
- 题意：
- 给出一个母串和一个子串且母串中存在子串的子序列，问你最多删除母串多少字符依然能让母串中存在子串的子序列。有俩个不同的难度，就是长度不同而已，这里直接写hard的做法。
- 题解：
- 最大分割情况只可能是两种，一种是最左端或者最右端删去一大段，另一种是中间任意两个字母间删去一大段
- 代码：
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxx = 200005; char s1[maxx],s2[maxx]; int pre[maxx],nex[maxx]; int main() { scanf("%s%s",s1,s2); int l1 = strlen(s1),l2 = strlen(s2); int t = 0; for(int i=0;i<l1;i++){ if(s1[i] == s2[t]){ pre[t] = i; t++; } if(t >= l2) break; } t = l2-1; for(int i=l1-1;i>=0;i--){ if(s1[i] == s2[t]){ nex[t] = i; t--; } if(t < 0) break; } int ans = max(nex[0],l1 - pre[l2-1] - 1); for(int i=1;i<l2;i++){ ans = max(ans,nex[i] - pre[i - 1]-1); } cout<<ans<<endl; return 0; }
题意：
给出n个人的体重，每个人可以选择增加1，较少1，或者不变体重。
问你最后最多有多少人的体重不一样，注意，体重不能减小到0
题解：
必须要往一个方向填充贪心。
代码：#include <bits/stdc++.h> using namespace std; #define ll long long const int maxx = 150010; int a[maxx],flag[maxx]; int main() { int n,ans = 0; cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } sort(a+1,a+1+n); flag[0] = 1; for(int i=1;i<=n;i++) { if(!flag[a[i] - 1]){ flag[a[i] - 1] = 1;ans++; } else if(!flag[a[i]]){ flag[a[i]] = 1;ans++; } else if(!flag[a[i] + 1]){ flag[a[i]+1] = 1;ans++; } } cout<<ans<<endl; return 0; }
题意：
给出n对数，每个数有俩个权值a和b，a代表学习这个技能的最小等级，b代表你学完这个技能后可以增加或者减少多的等级，问你能否学完所有的技能
题解：
优先队列+贪心
代码：#include <bits/stdc++.h> using namespace std; #define ll long long struct node{ int a,b; friend bool operator < (node p1,node p2){ return p1.a>p2.a; }//小 }; struct node2{ int a,b; friend bool operator < (node2 p1,node2 p2){ if(p1.a + p1.b != p2.a + p2.b) return p1.a + p1.b < p2.a + p2.b; return p1.a<p2.a; } }; priority_queue<node> q1; priority_queue<node2> q2; int main() { int n,r,a,b; scanf("%d %d",&n,&r); for(int i=1;i<=n;i++){ cin>>a>>b; if(b>=0) q1.push(node{a,b}); else q2.push(node2{a,b}); } while(!q1.empty()) { node now = q1.top(); q1.pop(); if(now.a > r){ cout<<"NO"<<endl; return 0; } r += now.b; } //cout<<r<<endl; while(!q2.empty()) { node2 now = q2.top(); q2.pop(); if(now.a > r){ cout<<"NO"<<endl; return 0; } r += now.b; } //cout<<r<<endl; if(r >= 0) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }
加油！
投递牛客等公司10个岗位 >
