A题
题意:n个数,每次选择两个数,第一个数-1,第二个数+1,但要保证操作后两个数非负,最多操作k次,问最小的序列
解:前面能减则减
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e3 + 10; int t,n,k,a[maxn]; void solve() { for(int i = 1;i < n; ++i) { if(k < a[i]) { a[i] -= k; a[n] += k; break; } else { k -= a[i]; a[n] += a[i]; a[i] = 0; } } for(int i = 1;i <= n; ++i) printf("%d%c",a[i],i == n?'\n':' '); } int main() { std::ios::sync_with_stdio(false); cin>>t; while(t--) { cin>>n>>k; for(int i = 1;i <= n; ++i) cin>>a[i]; solve(); } return 0; }B题
题意:n个数,每次选两个相邻的数x,y扔掉,然后放进去x^y,问最后能不能得到一个长度>=2的元素都相等的数组
解:刚开始没看到相邻wa了好久,异或和ans为0必然可以,否则就看ans在异或过程中出现过几次
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e3 + 10; int t,n,k,a[maxn],b[100],ans; bool check() { int s = 0,e = 0; for(int i = 1;i <= n; ++i) { s ^= a[i]; if(s == ans) { e++; s = 0; if(e > 1) return 1; } } return 0; } int main() { std::ios::sync_with_stdio(false); cin>>t; while(t--) { cin>>n; ans = 0; for(int i = 1;i <= n; ++i) { cin>>a[i]; ans ^= a[i]; } if(!ans || check()) printf("YES\n"); else printf("NO\n"); } return 0; }C题
题意:问怎删除序列里的数字,使得序列无法分成和相等的两部分
解:1)一个数组能否分成和相等的两部分
bool check() { int x = sum / 2; ///分成和都为x的两部分 dp[0] = 1; for(int i = 1;i <= n; ++i) { int u = x; while(u >= a[i]) dp[u] += dp[u - a[i]],u--; } if(dp[x] >= 2) return 1; }2) 和为奇数肯定不可以分成
没有想到的点是除最大公因数,因为想的是如果有奇数删奇数就可以,没有奇数的话就不知道该怎么处理,除了最大公因数之后,必然不会出现全部是偶数的现象。
#include<bits/stdc++.h> using namespace std; int a[105],dp[200010]; int n,d; int main() { cin>>n; d = 0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); d = __gcd(d,a[i]); } int S = 0; for(int i=1;i<=n;i++) a[i]/=d,S += a[i]; dp[0]=1; int id=0; for(int i=1;i<=n;i++) { if(a[i]&1)id=i; for(int j=S;j>=a[i];j--)dp[j]|=dp[j-a[i]]; } if(S % 2==1||dp[S/2]==0)printf("0"); else printf("1\n%d",id); }D题
题意:每次选择一个区间,将区间里的数分成若干个连续的区间,使每个区间内的lcm等于组内数的乘积,最少分成多少组
解:最少的组数肯定是出现次数最多的质数的出现次数(含有相同因子代表gcd不为1,肯定不能分到一组)
首先对于l,向右能扩展到r,那么对于L>l,扩展到的R>=r所以我们可以用双指针用O(n)复杂度预处理每个数能向右扩展多远
问题转化为[l,r]中间包含多少个这样长的子区间
倍增处理 f[i][j] = f[f[i][j - 1] + 1][j - 1]
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; bool vis[maxn]; vector<int>v[maxn]; int a[maxn],prim[maxn],f[maxn][20]; int n,q,tot,l,r; void init() ///预处理 { vis[0] = vis[1] = 1; tot = 1; for(int i = 2;i <= 100000; ++i) { if(!vis[i]) prim[tot++] = i; for(int j = 1;j < tot && prim[j] * i <= 100000; ++j) { vis[prim[j] * i] = 1; if(i % prim[j] == 0) break; } } for(int i = 1; i < tot; ++i) for(int x = prim[i]; x <= 100000; x += prim[i]) v[x].push_back(i); } int main() { std::ios::sync_with_stdio(false); init(); cin>>n>>q; memset(vis,0,sizeof(vis)); for(int i = 1;i <= n; ++i) cin>>a[i]; for(int i = 1,r = 0;i <= n; ++i) { for(; r < n; ++r) { int flag = 1; for(auto x: v[a[r + 1]]) { if(vis[x]) { flag = 0; break; } } if(!flag) break; for(auto x:v[a[r + 1]]) vis[x] = 1; } f[i][0] = r; for(auto x: v[a[i]]) vis[x] = 0; } for(int i = 1;i < 20; ++i) for(int j = 1;j <= n; ++j) if(f[j][i - 1]) f[j][i] = f[f[j][i - 1] + 1][i - 1]; while(q--) { cin>>l>>r; int ans = 0,x = l; for(int i = 19;i >= 0;--i) if(f[x][i] && f[x][i] <= r) x = f[x][i] + 1,ans += 1 << i; cout<<ans + (x <= r)<<endl; } return 0; }