2023 (ICPC) Jiangxi Provincial Contest ABCHIJKL

签到看是否 $S\cdot V\ge N$

#include <bits/stdc++.h>
using namespace std;void solve(){int n,s,v;cin>>n>>s>>v;if(s*v>=n) cout<<"1\n";else cout<<"0\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t = 1;cin>>t;while(t--) solve();return 0;
}

正难则反，考虑小于等于的个数不好考虑,我们可以用总数减去大于的情况

大于的情况怎么统计，我们发现大于只会出现在前一个数$b_{i-1}$加上 $a_i$ 就超过m的时候会出现，这个次数的总和相当于商,即 $\frac{b_n}{m}$

然后 $b_n=x+{\sum }_{i=1}^k{a}_i\ast \lfloor \frac{n}{k}\rfloor +{\sum }_{i=1}^{n\%k}{a}_i$ ,那么答案就是$n-\frac{b_n}{m}$

#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;constexpr int maxn = 1e6+10;
int k,n,m,x;
int a[maxn];
__int128 pre[maxn];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>k;for(int i = 1;i<=k;++i){cin>>a[i];}cin>>n>>m>>x;x%=m;for(int i = 1;i<=k;++i){a[i]%=m;pre[i]=pre[i-1]+a[i];}__int128 bn = x+__int128(n/k*pre[k])+pre[n%k];bn/=m;cout<<i64(n-bn);return 0;
}

队友写的，不太清楚，有空update

#include <bits/stdc++.h>
using namespace std;
#define int long longint n,p;
int a[1232100];
int b[10000100];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>p;int ji=0;int yi=0,er=0;for(int i = 1;i<=n;++i){cin>>a[i];ji^=(a[i]&1LL);a[i]-=1;a[i]%=(p+1);if(a[i]==p) a[i]=0;else if(a[i]==p-2) yi++;else if (a[i]==p-1) er++;else{if((a[i])%2==0) yi++;else a[i]=0;}}if(p&1){if(ji) cout<<"GOOD\n";else cout<<"BAD\n";return 0;}if(er%2==0 && yi%2==0) cout<<"BAD\n";else cout<<"GOOD\n";// b[0]=0;// b[1]=1;// for (int i=2;i<=1000000;i++)// {//     int tmp=1,flag=0;//     while (tmp<=i)//     {//         if (b[i-tmp]==0) flag=1;//         tmp*=p;//     }//     b[i]=flag;// }// for (int i=1;i<=10000;i++)// {//     cout<<a[i]<<" \n"[i%p+1==0];// }return 0;
}

我们发现如果前缀max一样肯定需要放在一起，把需要放在一起的数字看成物品，那么就相当于变成了有很多体积和价值一样的物品(可以重复)问能否可以恰好塞满$\frac{n}{2}$ 的空间，还可以注意到${\sum }_i^m{x}_i=n$ ,其中 $x_i$ 是每件物品的体积，我们想让种类尽可能的多，那么肯定是从1开始，公差为1的等差数列的体积是最优的，那么可以求出体积最大是 $\sqrt{n}$ ,那么种类最多也是那么多，我们对这 $\sqrt{n}$ 跑多重背包，用二进制优化即可通过本体，更优秀的，我们可以用bitset优化转移，可以跑的更快

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;constexpr int maxn = 5e5+10;
int n;
bitset<maxn> f;
inline void solve(){cin>>n;vector<int> p(n);int mx = 0;vector<int> b(n+1,0);vector<int> c;for(int i = 0;i<n;++i){f[i]=0;cin>>p[i];if(i==0){mx = i;continue;}if(p[i]>p[mx]){b[i-mx]++;mx = i;}}b[n-mx]++;for(int i = 1;i<=n;++i){if(b[i]==0) continue;int cnt=1;while(b[i]>cnt){b[i]-=cnt;c.push_back(i*cnt);cnt<<=1;}c.push_back(b[i]*i);}f[0]=1;for(auto &i:c){f|=(f<<i);if(f[n/2]){cout<<"Yes\n";return;}}cout<<"No\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int T;cin>>T;while (T--) {solve();}return 0;
}

签到，感觉有点诈骗，修改其实只和两端的有关，询问 $x$ 到 $y$ 路径中的点（不包括 $x$,$y$），那些被修改的边肯定是被 $xor$ 两次，相当于没有修改

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000100];
int b[1000100];
void solve(){int n,m,q,x,y,z,i;cin >> n>>m;for (i=1;i<n;i++) {cin>>x>>y>>z;a[x]=a[x] xor z;a[y]=a[y] xor z;}while (m--) {cin>>q;if (q==1) {cin>>x>>y>>z;a[x]=a[x] xor z;a[y]=a[y] xor z;}else {cin>>x;cout<<a[x]<<"\n";}}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t = 1;while(t--) solve();return 0;
}

添加的 $a$ 和 $b$ 都是小于等于 $10^5$ 。如果 $i$ 和 $a$ 的差距大于$\sqrt{10^5}$,那么他们的函数值之差足以抹平 二者 $b$ 之间的差距 ，所以每次查询只要往 $a$ 左右找 $\sqrt{n}$ 个点即可，时间复杂度 $O(n\sqrt{n})$

#include <bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int maxn = 1e5+10,D = 317;
int n,m;
int b[maxn];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i = 1;i<=n;++i) cin>>b[i];cin>>m;while(m--){int op,x,y;cin>>op;if(op==0){cin>>x>>y;if(y<b[x]) b[x]=y;}else{cin>>x;int l = max(1LL,x-D),r = min(n,x+D);int mi = 1e18;for(int i = l;i<=r;++i){mi = min(mi,(i-x)*(i-x)+b[i]);}cout<<mi<<"\n";}}return 0;
}

多练思维是真的有用的，K题没有想象中的那么难，我们发现交换只是让相邻两个数之间的差值换了个位置（自己手模一个算一下和旁边两个的差值即可发现）,所以我们只要把差值排个序就做完了

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000100];
int b[1000100];
void solve(){int n;cin >> n;for (int i=0;i<n;i++) cin >> a[i];int sum=a[0]-a[n-1];for (int i=1;i<n;i++) b[i-1]=-(a[i-1]-a[i]);sort(b,b+n);for (int i=1;i<n;i++) b[i]=b[i]+b[i-1];int m;cin >> m;for (int i=0;i<m;i++){int op,x;cin >> op >> x;if (op==0) continue;cout << sum+b[x-2] << "\n";}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t = 1;//cin>>t;while(t--) solve();return 0;
}

输出n-1即可

#include <bits/stdc++.h>
using namespace std;signed main(){int n;cin>>n;cout<<n-1;return 0;
}