T1 u
差分与前缀的综合练习。
分析数据范围，只能是在修改的时候$O(1)$做到，那么只能是像打标记一样处理那个三角形
正解是建立两个二位前缀和，一个控制竖向，一个控制斜向
每次在三角的左上，右下，左下几个位置分别打上加一或者减一的标记
之后$N^2$查询时直接将标记“下放”就可以求出正确的异或和
思路挺神的
知识点
差分与前缀
标记下放
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 inline int read(){
5 int x=0,f=1; char ch=getchar();
6 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
7 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
8 return x*f;
9 }
10 const int NN=4005;
11 int n,q;
12 int d1[NN][NN],d2[NN][NN];
13 namespace WSN{
14 inline int main(){
15 n=read(); q=read();
16 while(q--){
17 int r=read(),c=read(),l=read(),s=read();
18 d1[r][c]+=s;
19 d1[r+l][c]-=s;
20 d2[r][c+1]-=s;
21 d2[r+l][c+l+1]+=s;
22 }
23 int ans=0,tmp=0;
24 for(int i=1;i<=n;i++){
25 tmp=0;
26 for(int j=1;j<=n;j++){
27 tmp+=d1[i][j]+d2[i][j];
28 d1[i+1][j]+=d1[i][j];
29 d2[i+1][j+1]+=d2[i][j];
30 ans^=tmp;
31 }
32 }
33 printf("%lld\n",ans);
34 return 0;
35 }
36 }
37 signed main(){return WSN::main();}
View Code
T2 v
一看数据范围，就是知道是个状压，但是根本不懂如何定义数组。。
更何况还有一个后效性的问题。。。
但是如果足够暴力的将每一种可能的删球情况都枚举出来的话，就没事了
那么肯定会T，考虑记忆化搜索
我们设$m[sta]$表示在$sta$状态下的期望值
因为在进行$dfs$时状态会重复，考虑使用哈希表去重
然后就是在进行状压时候的状态转移，比较神
大概就是：
1 将数列向右移动几位
2 将数列往回移动那么多位-1，相当于去掉了一位
3 将原来数列里面的后几位提取过来，给那个位移了的数列拼起来
知识点：
记忆化搜索
状压dp
哈希表
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,k;char ch[35];
4 struct HASH{
5 struct edge{int to,next;};edge e[50000013];int head[50000013],tot; short leng[50000013],len; double val[50000013];
6 double &operator[](int sta){
7 int x=sta*len%50000013;
8 for(int i=head[x];i;i=e[i].next) if(e[i].to==sta&&leng[i]==len) return val[i];
9 e[++tot]=(edge){sta,head[x]}; leng[tot]=len; head[x]=tot; return val[tot]=-1.0;
10 }
11 }m;
12 inline double dp(int len,int sta){
13 // cout<<len<<endl;
14 if(len==n-k) return 0.0;
15 m.len=len; if(m[sta]>-0.5) return m[sta];//在返回记忆化值之前记录长度，否则会出现后效性
16 m[sta]=0;//记得定义初始状态值，否则样例返回-0.0（因为原本不定义初始值m[sta]为-1,减一后正好为-0.0）
17 int pos[35],st=sta;
18 for(int i=1;i<=len;i++) pos[i]=st&1,st>>=1;//复制原状态到数组备用(是反着赋值)
19 for(int i=1;i<=len/2;i++){
20 int st1=sta>>len-i+1<<len-i|sta&(1<<len-i)-1;//从左面删除
21 int j=len-i+1;
22 int st2=sta>>len-j+1<<len-j|sta&(1<<len-j)-1;//从右面删除
23 double ans1=dp(len-1,st1)+pos[j];
24 double ans2=dp(len-1,st2)+pos[i];
25 m.len=len; m[sta]+=2.0/len*max(ans1,ans2);
26 }
27 if(len&1){//如果是奇数就判断中间之前没有循环到的一位
28 int mid=len/2+1;
29 int st3=sta>>len-mid+1<<len-mid|sta&(1<<len-mid)-1;
30 double ans3=dp(len-1,st3)+pos[mid];
31 m.len=len; m[sta]+=1.0/len*ans3;
32 }
33 return m[sta];
34 }
35 namespace WSN{
36 inline int main(){
37 scanf("%d%d%s",&n,&k,ch+1); int sta=0;
38 for(int i=1;i<=n;i++) sta=sta<<1|(ch[i]=='W');
39 printf("%.10lf",dp(n,sta));
40 return 0;
41 }
42 }
43 signed main(){return WSN::main();}
View Code
T3 w
第一眼，可恶，又是$dp$。。
树形$dp$当时学的比较糟糕（不过假期讲课skyh大神讲过后明白了许多）
这题有两个难点
一个是关于状态的定义，
我们发现可以把c，d$xor$表示这个边是否需要反转
考虑最小操作次数，其实就是度数为奇数的点数/2，这里的度数指的是所连的最终状态与之前不一样的边数，包括必须翻和不必须。
那么我们开一个结构体记录度数为奇数的点数和链的长度，结构题数组$dp_{i,0/1}$表示$i$上面的一条边反转与否，并记录儿子的信息
第二个是分类讨论，
如果度数为奇，
度数为奇的儿子不用翻，之前是偶数儿子用翻取min
如果度数为偶，
度数为偶的儿子用翻，之前是偶数儿子不用翻取min
统计完儿子的信息就要把自己加进子树中。
如果当前点和父亲必须翻，为自己是奇数的个数，长度+1和自己是偶数的个数+1，长度+1取min。
如果当前点和父亲必须不翻，为自己是奇数的个数+1，长度和自己是偶数的个数，长度。
如果可翻可不翻，那么两种状态都会存在。
转移的时候使用中间量$w_1,w_2,n_1,n_2$1表示奇度数的转移信息，2同理表示偶数的
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int NN=1e5+5,inf=0x3f3f3f3f;
4 int n;
5 struct SNOW{int to,next,c;};SNOW e[NN<<1]; int head[NN],rp;
6 struct DP{
7 int sum,len;
8 DP(){}
9 DP(int x,int y){this->sum=x; this->len=y;}
10 DP operator+(DP x) const{
11 DP ans;
12 ans.len=len+x.len;
13 ans.sum=sum+x.sum;
14 return ans;
15 }
16 bool operator<(DP x) const{
17 return sum==x.sum? len<x.len : sum<x.sum;
18 }
19 }dp[NN][3];
20 inline void add(int x,int y,int z,int w){
21 e[++rp].to=y; e[rp].next=head[x]; e[rp].c=(w==2?2:z^w); head[x]=rp;
22 e[++rp].to=x; e[rp].next=head[y]; e[rp].c=(w==2?2:z^w); head[y]=rp;
23 }
24 inline void dfs(int f,int x,int opt){
25 DP w1=DP(inf,inf);
26 DP w2=DP(0,0);
27 for(int i=head[x];i;i=e[i].next){
28 int y=e[i].to;
29 if(y==f) continue;
30 dfs(x,y,e[i].c);
31 DP n1=min(w2+dp[y][1],w1+dp[y][0]);
32 DP n2=min(w1+dp[y][1],w2+dp[y][0]);
33 w1=n1; w2=n2;
34 }
35 if(opt==0){
36 dp[x][1]=DP(inf,inf);
37 dp[x][0]=min(DP(w1.sum+1,w1.len),w2);
38 }
39 else if(opt==1){
40 dp[x][1]=min(DP(w2.sum+1,w2.len+1),DP(w1.sum,w1.len+1));
41 dp[x][0]=DP(inf,inf);
42 }
43 else{
44 dp[x][1]=min(DP(w2.sum+1,w2.len+1),DP(w1.sum,w1.len+1));
45 dp[x][0]=min(DP(w1.sum+1,w1.len),w2);
46 }
47 }
48 namespace WSN{
49 inline int main(){
50 scanf("%d",&n);
51 for(int i=1,a,b,c,d;i<n;i++) scanf("%d%d%d%d",&a,&b,&c,&d),add(a,b,c,d);
52 dfs(0,1,0); printf("%d %d\n",dp[1][0].sum/2,dp[1][0].len);
53 return 0;
54 }
55 }
56 signed main(){return WSN::main();}
View Code