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

团队训练赛时ac 710011.令xa|b,yab, 因为abxy,又abxy(这个其实很好想{01}{10}在|会变成1记录存在进位二者等价可知{x,y}{a,b},等价xa,yb | xb,ya;2.aa|b,bab 等价 a包含b, 反过来同理3.我们来看b包含a的情况b取0a只能取0, b取1a可以取0|1》{001}{011}4.由容斥原理a包含b或b包含a的可能数a包含bb包含a-ab;a包含b*2-ab;5.求b包含a,考虑数位dp,观察每一位怎么取取数只有上述三种可能创建一个状态位记录当前两个数的上下界是否严格逼近依法更新状态即可dp[当前位数][状态位mask] mask _ _ _ _ (upa,loa,upb,lob)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,mod998244353,M1e610;int lowbit(int x){return x(-x);}vectorintMin{0,0,1};vectorintMax{0,1,1};void solve(){string a,b;cinab;int asa.size();int bsb.size();int dtbs-as;/*fr(i,1,dt){a0a;}*/if (asbs)astring(dt,0)a;// a a;// b b;int nbs;int numa0;int numb0;vectorvectorintdp(n2,vectorint(16,0));dp[0][15]1;fr(i,0,n-1){int abita[i]-0;int bbitb[i]-0;numanuma*2abit;numa%mod;numbnumb*2bbit;numb%mod;fr(j,0,15){if(dp[i][j]0)continue;int Predp[i][j];int upa(j3)1;int loa(j2)1;int upb(j1)1;int lobj1;fr(k,0,2){int cxMin[k];int cyMax[k];if(upacxbbit)continue;if(loacxabit)continue;if(upbcybbit)continue;if(lobcyabit)continue;int nxt0;if(upacxbbit)nxt|8;if(loacxabit)nxt|4;if(upbcybbit)nxt|2;if(lobcyabit)nxt|1;//dp[i1][nxt](dp[i][nxt]Premod)%mod;dp[i1][nxt]Pre;if(dp[i1][nxt]mod)dp[i1][nxt]-mod;}}}int res0;fr(i,0,15){res(resdp[n][i]mod)%mod;}res%mod;int ans2*res-(numb-numa1mod)%mod;ans(ans%modmod)%mod;// ansabs(ans-mod);cans;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1004构造 n-2个12,nk即可#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;fr(i,1,n-2){cout1 ;}cout2 nk;cout\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1006签到10071.考虑失败的前一个状态必败态假设此时取了一个数x导致失败S^x0,Sx;如果此时集合中存在y!x,则取y,S^y!0,更优故此时集合不存在y!x此时集合全部由x构成而s!0x的个数为奇数2.又S0先手必败所以可以先猜测一下必胜态为S!0,|S|为偶数3.我们可以口胡一下这个结论的正确性对于每一次取如果当时S中的元素不唯一我们一定会取y!S,直到a.所有元素被取完此时其实就是奇偶判断偶数先手必胜b.剩余元素均相同那么必败态等价奇数个元素则必胜态就是偶数个元素4.实现S!0,|S|为偶数|S|为偶数-|S|为偶数-S0;前缀和计数即可code:(队友敲的#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;}LL find(LL x){LL ans1;for(int i1;ix;i){ansfind(x-i);}return ans;}bool check(vectorLLa,int l,int r){unordered_mapLL,LLmp;LL len0,sum0;for(int il;ir;i){mp[a[i]];sumsum^a[i];if(mp[a[i]]%20){len--;}else{len;}}if(len0||len%21||sum0)return false;else return true;}void solve(){LL n;cinn;vectorLLa(n1);for(int i1;in;i){cina[i];}unordered_mapLL,LLmp,mp1[3];LL ans0,sum0;mp1[2][0]1;for(int i1;in;i){ansi/2;sumsum^a[i];LL ci%2;if(c0)c2;ans-mp1[c][sum];mp1[c][sum];// coutsum ;}//coutendl;LL ans1n*(n1)/2-ans;coutans ans1endl;}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);LL T1;cinT;while(T--){solve();}}1008签到1009code:#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,m;cinnm;if(nm){swap(n,m);}if((n%21)||(m%21)){cout(n*m1)/2\n;return;}int Max1m*(n/2-1);Max1max(Max1,(int)0);int Max2n*(m/2-1);Max2max(Max2,(int)0);int ansmax(Max1,Max2);cans;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1010:有点点递归的思想1.和为x的序列 有2^(x-1)个对于从高到低的数位贪心的从1开始考虑如果当前的k大于由这个数开头的序列数则把这个数1确认开头的数后后面的序列种数会相应减少为2^(x-k),直到小于开头数确认下后面序列的种数则该位数确定2.往下递归即可code:(队友敲的#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)#pragma GCC optimize(2)using namespace std;const int N1e6;const int M21e181;vectorintm2(N1);int x,k;void init(){m2[0]1;for(int i1;iN;i){m2[i]min(M2,m2[i-1]*2);}}int f(){//dbg(k);int t1;while(1){if(km2[x-t])k-m2[x-t],t;else return t;if(tx)return x;}}void solve(){cinxk;if(xk){for(int i1;ik;i)cout1 ;cout\n;return;}vectorintans;k;while((k--)1){int yf();ans.push_back(y);x-y;}for(int it:ans)coutit ;cout\n;}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);init();int T1;cinT;while(T--){solve();}//cout(int)pow(2,1e3);return 0;}