1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 int n,q,c1[1050][1050],c2[1050][1050],c3[1050][1050]; 5 signed main(){ 6 scanf("%lld%lld",&n,&q); 7 for(int i=1;i<=q;++i){ 8 int x,y,len,s;scanf("%lld%lld%lld%lld",&x,&y,&len,&s); 9 c1[x][y]+=s;if(x+len<=n) c1[x+len][y]-=s; 10 if(y+1<=n) c2[x][y+1]-=s;if(x+len<=n&&y+len+1<=n) c2[x+len][y+len+1]+=s; 11 } 12 for(int j=1;j<=n;++j) 13 for(int i=1;i<=n;++i) 14 c1[i][j]+=c1[i-1][j]; 15 for(int i=1;i<=n;++i) 16 for(int j=1;j<=n;++j) 17 c2[i][j]+=c2[i-1][j-1]; 18 int ans=0; 19 for(int i=1;i<=n;++i){ 20 for(int j=1;j<=n;++j) c3[i][j]=c1[i][j]+c2[i][j]; 21 for(int j=1;j<=n;++j) c3[i][j]+=c3[i][j-1]; 22 for(int j=1;j<=n;++j) ans^=c3[i][j]; 23 } 24 printf("%lld\n",ans); 25 return 0; 26 }
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct Hashmap{ 4 struct Edge{int nxt,len,sta;double w;}l[4000000]; 5 int len,cnt,head[30000024]; 6 double &operator[](int sta){ 7 int Head=1LL*sta*len%30000023; 8 for(int i=head[Head];i;i=l[i].nxt) if(sta==l[i].sta&&len==l[i].len) return l[i].w; 9 l[++cnt]=(Edge){head[Head],len,sta,-1.0}; 10 head[Head]=cnt;return l[cnt].w; 11 } 12 }Map; 13 char s[35]; 14 int st,n,k; 15 int Get(int sta,int w){return (sta&((1<<w)-1))+((sta>>(w+1))<<w);} 16 double dfs(int x,int sta){ 17 if(x==n-k) return 0.000; 18 Map.len=x;if(Map[sta]!=-1) return Map[sta]; 19 Map[sta]=0; 20 for(int i=0;i<=x/2-1;++i){ 21 bool al1=sta&(1<<i),al2=sta&(1<<x-1-i); 22 double t1=dfs(x-1,Get(sta,i))+al1; 23 double t2=dfs(x-1,Get(sta,x-1-i))+al2; 24 Map.len=x;Map[sta]+=2.0*max(t1,t2)/x; 25 } 26 if(x&1){ 27 bool al1=sta&(1<<(x/2)); 28 double tt=dfs(x-1,Get(sta,x/2))+al1; 29 Map.len=x;Map[sta]+=1.0*tt/x; 30 } 31 return Map[sta]; 32 } 33 int main(){ 34 scanf("%d%d%s",&n,&k,s+1); 35 for(int i=n;i;--i) st<<=1,st+=(s[i]=='W'); 36 printf("%.10lf\n",dfs(n,st)); 37 }
A. u
容易发现，一个下三角形可以用差分的差分来维护。
为什么要差分的差分？首先我们考虑最native的差分就是在每一行对应的首和尾去差分。
复杂度$O(qn)$
考虑到我们差分的位置似乎也是固定的？即一种差分是竖的的，一种差分是斜着的。
那么我们分两种差分的情况对差分的数值假装它是真正的值对它进行差分即可。
$O(q+n^2+n^2)$
B. v
首先应该想到应该和状压有点关系。
考虑状压的东西，容易发现我们只关注每种长度的情况下剩余球的颜色序列，而不去关注每个球的取/不取。
那么我们考虑dp，设dp[i][[sta]表示当前考虑到第i次摸球，此时的球颜色序列为sta的最大期望值。
我们发现一定有很多的重复的情况就是说从i的不同sta通过摸球不同到了相同的dp[i+1][sta1]
注意到这样的转移是不对的，因为你这次要摸对称的哪个球是由它们分别的期望值决定的！即dp[i+1][sta1]与dp[i+1][sta2]
所以要倒着转移
可以dfs记忆化，也可以倒序dp，题解上说不同的状态数为$sigma_{i=1->n}Fib(i)$，不懂。
还有因为状态有些大，要用map
一种手打map的[]好方法.
struct Hashmap{ struct Edge{int nxt,len,sta;double w;}l[4000000]; int len,cnt,head[30000024]; double &operator[](int sta){ int Head=1LL*sta*len%30000023; for(int i=head[Head];i;i=l[i].nxt) if(sta==l[i].sta&&len==l[i].len) return l[i].w; l[++cnt]=(Edge){head[Head],len,sta,-1.0}; head[Head]=cnt;return l[cnt].w; } }Map;
C. w
我没水平
D. 相逢是问候
不会滚