10.7 div2复现赛 P14178 「FAOI-R8」Jueves 可以发现一些性质： 当 s=t 时，显然答案为 0 否则，最短路一定是连接 s 与 t 的那条边，因为 (a_u xor a_v)+(a_u or a_v)+(a_u and a_v) > a_u。 所以代码非常简单： #include using namespace std; #define int long long const int N=5e5+5; int T,n,s,t; int a[N]; signed main(){ cin>>T; while(T--){ cin>>n>>s>>t; for(int i=1;i>a[i]; if(s==t) cout `#include using namespace std; #define int long long const int N=5e5+5; int T,n,s,t; int a[N]; signed main(){ cin>>T; while(T--){ cin>>n>>s>>t; for(int i=1;i>a[i]; if(s==t) cout0 else couta[s]^a[t])+(a[s]|a[t])+(a[s]&a[t]) } return 0; }` P14179 「FAOI-R8」喵了个喵 V 首先无视 m 的取值根据题意模拟求出字典序最小的答案数组， 若此时 m0，则再次按照性质从大到小尽可能地匀给当前位置， 然后就能得出答案了。 代码： #include using namespace std; #define int long long const int N=1e6+5; int T; int n,d,m; int a[N]; bool b[N]; signed main(){ cin>>T; while(T--){ int y=1; cin>>n>>d>>m; for(int i=1;i>b[i],a[i]=0;; for(int i=1;i0){ for(int i=n;i>=1;i--){ if(!m) break; if(b[i]){ if(i==n){ a[i]+=(m-(m%d)),m=m%d; continue; } int cha=(a[i+1]-(a[i+1]%d))-a[i]; if(chaa[i+1]&&i!=n)) y=0; } } if(y==0||m!=0) cout `#include using namespace std; #define int long long const int N=1e6+5; int T; int n,d,m; int a[N]; bool b[N]; signed main(){ cin>>T; while(T--){ int y=1; cin>>n>>d>>m; for(int i=1;i>b[i],a[i]=0;; for(int i=1;i a[i]+=a[i-1]; if(b[i]){ if(a[i]%d==0){ m-=a[i]; continue; } int add=d-(a[i]%d); a[i]+=add,m-=a[i]; if(m0) y=0; } else{ if(a[i]%d!=0){ m-=a[i]; continue; } a[i]++,m-=a[i]; if(m0) y=0; } } if(m>0){ for(int i=n;i>=1;i--){ if(!m) break; if(b[i]){ if(i==n){ a[i]+=(m-(m%d)),m=m%d; continue; } int cha=(a[i+1]-(a[i+1]%d))-a[i]; if(cha a[i]+=cha; m-=cha; } else{ a[i]+=(m-(m%d)),m=m%d; } } else{ if(i==n||ma[i+1]-a[i]){ if((a[i]+m)%d==0) a[i]+=m-1,m=1; else a[i]+=m,m=0; } else{ if(a[i+1]%d==0) m-=a[i+1]-a[i]-1,a[i]=a[i+1]-1; else m-=a[i+1]-a[i],a[i]=a[i+1]; } } if(m0||(a[i]>a[i+1]&&i!=n)) y=0; } } if(y==0||m!=0) cout"No\n"; else{ for(int i=1;ia[i]" "; cout"\n"; } } return 0; }` P1651 塔 差值 DP。 设选到了第 i 个木块，左塔减右塔的值为 j 时，左塔最高的高度为 dp_{i,j}。 就可以分类讨论 a_i 是不放还是放在左塔还是放在右塔。 注意到 j 的值是会小于零的，所以我们给 j 整体加上 500000 就可以了。 代码： #include using namespace std; #define int long long const int N=1e6+5; int n,ans; int a[55],dp[N],dp1[N]; signed main(){ memset(dp,128,sizeof dp); memset(dp1,128,sizeof dp1); cin>>n; for(int i=1;i>a[i]; dp1[500000]=0; for(int i=1;i=0) dp[j]=max(dp[j],dp1[j-a[i]]+a[i]); if(j+a[i]0) cout `#include using namespace std; #define int long long const int N=1e6+5; int n,ans; int a[55],dp[N],dp1[N]; signed main(){ memset(dp,128,sizeof dp); memset(dp1,128,sizeof dp1); cin>>n; for(int i=1;i>a[i]; dp1[500000]=0; for(int i=1;i for(int j=0;j dp[j]=max(dp[j],dp1[j]); if(j-a[i]>=0) dp[j]=max(dp[j],dp1[j-a[i]]+a[i]); if(j+a[i]dp[j]=max(dp[j],dp1[j+a[i]]); if(j==500000) ans=max(ans,dp[j]); } for(int j=0;j dp1[j]=dp[j]; } } if(ans>0) cout else cout1; return 0; }`
10.7 div2复现赛
笔记