2026“钉耙编程”中国大学生算法设计春季联赛（1）题解/复盘

团队vp;赛时AC81001:1.很明显能看出本题的背景是巴什博弈等价 f mod (k1) 0;2.处理 x*k^(xy)y/(k1)的情况原式等价 x*((k1)-1)^(xy)/(k1) (-1)^(xy)xy/(k1)1.xy 1 y-x mod k1 kmax(x~y),而xy 1,x!y,所以永远不可能取到0;2.xy %2 0 yx mod k1 0 等价 xyk1;所以失败情况只有 xyk1 的情况最终答案 ansn*n-cnt*2;3.现在想怎么求 aiajmax of a(i~j) 1的情况数题目给出的数据范围是1e5级别考虑遍历max的情况下往两边扩展L,R,(这是一个基础的栈预处理O(n)级别开一个map记录每一个数出现的位置,对于一边的一个数我们在另一边需要的数是确定的二分查找另一边那个数对应的位置数组的边界相减即时当前该数能够达成条件的个数4.对于一个max用启发式的思想取LR,中那个较小的数遍历然后在另一边二分查找code:#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e410,mod1e97,M1e610;int lowbit(int x){return x(-x);}void solve(){int n;cinn;vectorinta(n1);fr(i,1,n){cina[i];}//aiajk1int ans0;vectorintL(n1),R(n1);stackintst1,st2;fr(i,1,n){while(!st1.empty()a[st1.top()]a[i]){st1.pop();}L[i](st1.empty()?1:st1.top()1);st1.push(i);}for(int in;i1;i--){while(!st2.empty()a[st2.top()]a[i]){st2.pop();}R[i](st2.empty()?n:st2.top()-1);st2.push(i);}mapint,vectorintmp;fr(i,1,n){mp[a[i]].pb(i);}fr(mid,1,n){if(mid-L[mid]R[mid]-mid){fr(i,L[mid],mid){if(mp.count(a[mid]1-a[i])){auto vmp[a[mid]1-a[i]];ans(upper_bound(all(v),R[mid])-lower_bound(all(v),mid));}}}else{fr(j,mid,R[mid]){if(mp.count(a[mid]1-a[j])){auto vmp[a[mid]1-a[j]];ans(upper_bound(all(v),mid)-lower_bound(all(v),L[mid]));}}}}ansn*n-2*ans;cans;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}10021.等价于所有前缀和%k不为0且不相同2.可能前缀和仅k-1种超过直接输出-13.开始设定值为1往下累加记录出现过的mod k的值出现过继续往下累加code:#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e410,mod1e97,M1e610;int lowbit(int x){return x(-x);}void solve(){int n,k;cinnk;if(nk){cout-1\n;return;}vectorboolvis(k1);vectorinta(n1);vis[0]1;int sum0;fr(i,1,n){int nxt(a[i-1]1);sumnxt;sum%k;int cnt0;while(vis[sum]){sum(sum1)%k;cnt;}a[i]nxtcnt;vis[sum]1;}fr(i,1,n){couta[i] ;}cout\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1003 MANACHER没学好不会1004抑或哈希前缀和预处理模板题不难看出本题的核心本质其实就是所有质因子相乘要求质数因子的幂次为奇数那么对于两个数ai,ai1,相乘在因子幂次奇偶性上等价抑或即将因子的幂次抑或可同样表示状态的前缀和变化令tag为需要达成的状态now为当前因子幂次抑或前缀和将tag^now即前面需要出现的状态将前面出现过的该种状态的个数累加现在考虑每个数的不同因子幂次这一状态如何表示定义一个unsigned long long 表示幂次因子为奇数的质数的抑或集合这样同时满足维护所有状态/状态改变#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;typedef unsigned long long ull;const int N1000005,mod1e97,M1e610;int lowbit(int x){return x(-x);}mt19937_64 rg(random_device{}());bool vis[N];ull hsh[N];void init(){for(int i2;iN;i){if(!vis[i]){hsh[i]rg();for(int jii;jN;ji){hsh[j]hsh[j/i]^hsh[i];vis[j]1;}}}}void solve(){int n,x;cinnx;ull taghsh[x];ull cur0;unordered_mapull,intmp;mp.reserve(n);int ans0;mp[0]1;int val;fr(i,1,n){cinval;cur^hsh[val];ull nedtag^cur;if(mp.count(ned)){ansmp[ned];}mp[cur];}cans;}signed main(){GG;int _t1;//cin_t;init();while(_t--){solve();}}1005二分/逐次累×判断code:#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e410,mod1e97,M1e610;int lowbit(int x){return x(-x);}int n,k;bool check(int x){if(x0)return 1;if(x1)return n1;int res1;fr(i,1,k){if(n/xres){return false;}res*x;}return resn;}void solve(){cinnk;int l0;int r1e9;int ans0;while(lr){int mid(lr)1;if(check(mid)){lmid1;}else{rmid-1;}}coutr\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1006:队友敲的#include bits/stdc.husing namespace std;using LL long long;#define endl \nLL mod1e97;LL ksm(LL a,LL n){LL res1;while(n){if(n1)resres*a;aa*a;n/2;}return res;}struct str{LL s,d;};bool cmp(str a,str b){if(a.sb.s)return a.db.d;return a.sb.s;}void solve(){LL n;cinn;vectorstra(n1);for(int i1;in;i){cina[i].sa[i].d;}sort(a.begin()1,a.end(),cmp);LL ans0;for(int i1;in;i){if(a[i].sans){ansa[i].d;}else{ansa[i].sa[i].d;}}coutansendl;}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);LL T1;cinT;while(T--){solve();}}1007队友敲的#include bits/stdc.husing namespace std;using LL long long;#define endl \nLL mod1e97;LL ksm(LL a,LL n){LL res1;while(n){if(n1)resres*a;aa*a;n/2;if(res1e9)return 1e9;}return res;}struct str{LL s,d;};bool cmp(str a,str b){if(a.sb.s)return a.db.d;return a.sb.s;}void solve(){LL n;cinn;vectorLLa(n1);for(int i1;in;i){cina[i];}vectorvectorLLedag(n1);for(int i1;in;i){int u,v;cinuv;edag[u].push_back(v);edag[v].push_back(u);}vectorLLson(n1),cnt(n1);auto dfs[](autoself,int x,int fa)-void{LL sum0,t0;cnt[x]1;for(int y:edag[x]){if(yfa)continue;self(self,y,x);cnt[x]cnt[y];if(cnt[y]sum){sumcnt[y];ty;}}son[x]t;};dfs(dfs,1,-1);vectorLLans(n1),w(n1);auto dfs1[](autoself,int x,int fa)-void{LL sum1e18;w[x]a[x];for(int y:edag[x]){if(yfa)continue;self(self,y,x);summin(sum,ans[y]);w[x]w[y];}for(int y:edag[x]){if(yfa)continue;w[x]cnt[y]*(ans[y]-sum);}if(w[x]sum){w[x]-sum;ans[x]sum;}else{ans[x](sum*(cnt[x]-1)w[x])/cnt[x];w[x](sum*(cnt[x]-1)w[x])-cnt[x]*ans[x];}};dfs1(dfs1,1,-1);for(int i1;in;i)coutans[i] ;coutendl;}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);LL T1;cinT;while(T--){solve();}}1008存在因数跟自己的值取lcm;求ans,二者取gcdcode:#includebits/stdc.h#define int long long#define pii pairint,int#define endl \n#define fi first#define se second#define dbg(x) cout#x xendl;#define dbg2(x,y) cout#x x #y yendl;#define dbg3(x,y,z) cout#x x #y y #z zendl;#define forn for(int i1;in;i)#define form for(int i1;im;i)#pragma GCC optimize(2)using namespace std;const int N2e510;int a[N];int lcm(int x,int y){return x*y/(__gcd(x,y));}void solve(){int n,m,q;cinnmq;forn a[i]1;form{int x,y,g;cinxyg;a[x]lcm(a[x],g);a[y]lcm(a[y],g);}while(q--){int x,y;cinxy;cout(__gcd(a[x],a[y]))\n;}}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T1;cinT;while(T--){solve();}return 0;}