250
TrySail
題意：把一個數列分成非空的三組，要求每組異或和的和最大(0≤a[i]≤255,n<=50)

分析：由于異或有減法，所以只要確定兩組的異或值，第三組的異或值就確定了，因此可以dp[i][j]代表第一組異或和為i，第二組異或和為j是否可能，注意到取到最大值的三組必然是非空的，因為有a^b<=a+b

500
DistinguishableSetDiv1
題意：問有多少種選擇問題的方法，使得n個人對這些問題的回答互不相同,n<=1000,問題總數<=20

分析：對于任意兩個人，我們可以處理出一個mask代表這兩個人哪些位置相同，顯然選擇mask和mask的子集都是不滿足要求的，因此求個高維前綴和就可以了

1000
SRMDiv0Easy
初始有一個數列，接著有Q次操作，每次給L[i]~R[i]加一個位于X[i]和Y[i]之間的數，最后要求每個數相同，問那個數最大可以是多少

分析：差分后轉化為有源匯有上下界的網絡流；這種類型的題目做法就是先連t->s流量為無窮，然后求可行流(注意可行流的連邊方法)；求完之后再在殘量網絡上求最大流就是答案

#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <fstream> #include <queue> using namespace std; const int Maxe=10000,Maxn=222,Inf=1e9; struct E{int v,c;E(){}E(int v,int c):v(v),c(c){} }e[Maxe]; class SRMDiv0Easy {public:int ne;vector<int>G[Maxn];int m;int cnt[Maxn];int cur[Maxn];int h[Maxn];int must[Maxe];void add(int u,int v,int c){e[ne]=E(v,c);G[u].push_back(ne++);e[ne]=E(u,0);G[v].push_back(ne++);}bool bfs(int st,int ed){for(int i=0;i<=max(st,ed);i++)h[i]=i==st?0:Inf;queue<int>q;q.push(st);while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<G[u].size();i++){int id=G[u][i];if(e[id].c){if(h[e[id].v]==Inf){h[e[id].v]=h[u]+1;q.push(e[id].v);}}}}return h[ed]!=Inf;}int dfs(int u,int ed,int a){if(u==ed||!a)return a;int ret=0;for(int &i=cur[u];i<G[u].size();i++){int id=G[u][i];int v=e[id].v,c=e[id].c;if(h[v]==h[u]+1&&c){int b=dfs(v,ed,min(a,c));a-=b;ret+=b;e[id].c-=b;e[id^1].c+=b;}}return ret;}int solve(int st,int ed){/*for(int i=0;i<=tt;i++){printf("ver%d:\n",i);for(int j=0;j<G[i].size();j++){int id=G[i][j];printf("v=%d c=%d ",e[id].v,e[id].c);}puts("");}*/int flow=0;while(bfs(st,ed)){memset(cur,0,sizeof(cur));flow+=dfs(st,ed,Inf);}return flow;}int get(int N, vector<int> L, vector<int> R, vector<int> X, vector<int> Y) {int s=N+1,t=N+2,ss=t+1,tt=t+2;memset(cnt,0,sizeof(cnt));ne=0;m=L.size();for(int i=0;i<=tt;i++)G[i].clear();for(int i=0;i<m;i++){add(L[i],R[i]+1,Y[i]-X[i]);cnt[L[i]]+=X[i];//liu chucnt[R[i]+1]-=X[i];}int tot=0;for(int i=0;i<=N;i++){if(!cnt[i])continue;if(cnt[i]>0)add(i,tt,cnt[i]),tot+=cnt[i];else add(ss,i,-cnt[i]);}add(s,0,Inf);int tar=ne-1;add(N,t,Inf);add(t,s,Inf);int ans=solve(ss,tt);if(ans!=tot)return -1;solve(s,t);return e[tar].c;return 0;} };

總結

以上是生活随笔為你收集整理的SRM694的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。