湖南集训day3
?
難度：☆☆☆☆☆☆☆
此時相望不相聞，愿逐月華流照君
?
?
/* 23 233 223 啦啦啦德瑪西亞 */ #include<iostream> #include<cstdio> #include<cstring>#define N 1000007using namespace std; int n,m,ans; char a[N];int main() {freopen("trans.in","r",stdin);freopen("trans.out","w",stdout);while(~scanf("%d%d%s",&n,&m,a)){for(int i=0; i<n; i++){if(!m) break;if(a[i]=='2' && a[i+1]=='2' && a[i+2]=='3'){if(i%2==0){if(m%2==0) break;else{a[i+1]='3';break;}}else{m--;a[i+2]='2';continue;}}else if(a[i]=='2' && a[i+1]=='3' && a[i+2]=='3'){if(i%2==1){a[i]='3';m--;continue;}else{if(m%2==0) break;else{a[i+1]='2';break;}}}else if(a[i]=='2' && a[i+1]=='3'){m--;if(i%2) a[i]='3';else a[i+1]='2';}}printf("%s",a);printf("\n");}fclose(stdin);fclose(stdout);return 0; }?
/* 把豆豆和磚塊丟在一起dp f[i][j][k]:到第i行,蛇的長度還剩下j,從k位置出第i行的最大得分 g[j][l][r]:蛇的長度剩下j,從當(dāng)前行l(wèi)到r區(qū)間內(nèi)仍為死亡的最大得分 初始化:對于每個i，g[j][k][k]=f[i-1][j-a[i][k]][k]+max(-a[i][k],0) 為初始狀態(tài) 方程g[j][l][r] = max(g[j-a[i][l]][l+1][r] + max(-a[i][j],0),g[j-a[i][r]][l][r-1]+max(-a[i][k],0)); 最后f[i][j][k] = max{g[j][l][r](1≤l≤k ≤r ≤5)} */ #include<iostream> #include<cstdio> #include<cstring>#define N 207 #define M 10005using namespace std; int a[N][5],f[N][M][5],g[M][5][5]; bool flag[N][4]; int n,m,maxi,ans,val;inline int read() {int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; }int main() {freopen("snakevsblock.in","r",stdin);freopen("snakevsblock.out","w",stdout);n=read();int x,y;for(int i=1;i<=n;i++) for(int j=0;j<5;j++)a[i][j]=read();m=read();for(int i=1;i<=m;i++){x=read();y=read();flag[x][y-1]=1;}memset(f,-0x7f7f7f,sizeof f);f[0][4][2]=0;maxi=n*50;for(int i=1;i<=n;i++){memset(g,-0x7f7f7f,sizeof g);for(int j=0;j<=maxi;j++)for(int k=0;k<5;k++)if(j-a[i][k]>=0 && j-a[i][k]<=maxi)f[i][j][k]=g[j][k][k]=f[i-1][j-a[i][k]][k]+max(-a[i][k],0);for(int l=1;l<=4;l++)for(int j=0,k=j+l;k<5;j++,k++)for(int v=0;v<=maxi;v++){if(!flag[i][j] && (val=v-a[i][j])>=0 && val<=maxi) g[v][j][k] = g[val][j + 1][k] + max(-a[i][j], 0);//g[v][j][k]=max(g[v][j][k],g[val][j+1][k]+max(-a[i][j],0));if(!flag[i][k-1]&& (val=v-a[i][k])>=0 && val<=maxi) g[v][j][k]=max(g[v][j][k],g[val][j][k-1]+max(-a[i][k],0));for(int to=j;to<=k;to++) f[i][v][to]=max(f[i][v][to],g[v][j][k]);}}for(int i=0;i<=n;i++)for(int j=0;j<=maxi;j++)for(int k=0;k<5;k++)ans=max(f[i][j][k],ans);printf("%d\n",ans);return 0; }?
、
不會不會不會不會不會不會就不會................................................................................................
暫時棄療
題解：
?
?
?
std：
#include <bits/stdc++.h> using namespace std; int n, m, P, u, v, to[200005], nxt[200005], p[100005], deep[100005], q[500005][2]; int son[100005], fa[100005], size[100005], top[100005], dfsx[100005], cnt, ans; int lca[500005], Q[500005], lr[100005][2]; int sta[100005]; bool flag[400005]; void dfs(int x) {size[x] = 1;for (int i = p[x]; i != -1; i = nxt[i])if (to[i] != fa[x]){fa[to[i]] = x;deep[to[i]] = deep[x] + 1;dfs(to[i]);if (son[x] == -1 || size[to[i]] > size[son[x]]) son[x] = to[i];size[x] += size[to[i]];} } void dfs1(int x) {dfsx[x] = ++cnt;if (son[x] != -1) top[son[x]] = top[x], dfs1(son[x]);for (int i = p[x]; i != -1; i = nxt[i])if (to[i] != fa[x] && to[i] != son[x])top[to[i]] = to[i], dfs1(to[i]); } int findlca(int x, int y) {while (1){if (top[x] == top[y]) return deep[x] > deep[y]? y : x;if (deep[top[x]] > deep[top[y]]) x = fa[top[x]];else y = fa[top[y]];} } bool query(int x, int l, int r, int ll, int rr) {if (l == ll && r == rr) return flag[x];int mid = (l + r) >> 1, L = x << 1, R = L | 1;if (rr <= mid) return query(L, l, mid, ll, rr);else if (ll > mid) return query(R, mid + 1, r, ll, rr);else return query(L, l, mid, ll, mid) | query(R, mid + 1, r, mid + 1, rr); } void modify(int x, int l, int r, int to) {flag[x] = true;if (l == r) return;int mid = (l + r) >> 1, L = x << 1, R = L | 1;if (to <= mid) modify(L, l, mid, to);else modify(R, mid + 1, r, to); } bool Query(int x, int y) {while (1){if (top[x] == top[y]){if (deep[x] < deep[y]) return query(1, 1, cnt, dfsx[x], dfsx[y]);else return query(1, 1, cnt, dfsx[y], dfsx[x]);}if (deep[top[x]] > deep[top[y]])if (query(1, 1, cnt, dfsx[top[x]], dfsx[x])) return true;else x = fa[top[x]];else{if (query(1, 1, cnt, dfsx[top[y]], dfsx[y])) return true;else y = fa[top[y]];}} } void work(int x) {for (int i = p[x]; i != -1; i = nxt[i])if (to[i] != fa[x])work(to[i]);for (int i = lr[x][0]; i <= lr[x][1]; i++)if (!Query(q[Q[i]][0], q[Q[i]][1])){modify(1, 1, cnt, dfsx[x]);sta[++ans] = x;return;} } bool cmp(int x, int y) {return lca[x] < lca[y];} int main() {freopen("ping.in","r",stdin);freopen("ping.out","w",stdout);scanf("%d%d", &n, &m);for (int i = 0; i <= n; i++) p[i] = son[i] = -1, top[i] = size[i] = fa[i] = deep[i] = 0;for (int i = 1; i <= n * 4; i++) flag[i] = false;for (int i = 1; i <= m; i++){scanf("%d%d", &u, &v);u--, v--;to[i * 2 - 1] = v;nxt[i * 2 - 1] = p[u];p[u] = i * 2 - 1;to[i * 2] = u;nxt[i * 2] = p[v];p[v] = i * 2;}deep[0] = 1;dfs(0);cnt = 0;dfs1(0);scanf("%d", &P);for (int i = 1; i <= P; i++){scanf("%d%d", &u, &v);u--, v--;q[i][0] = u, q[i][1] = v;lca[i] = findlca(u, v);Q[i] = i;}sort(Q + 1, Q + P + 1, cmp);for (int i = 0; i <= n; i++) lr[i][0] = P + 1, lr[i][1] = 0;for (int i = 1; i <= P; i++){lr[lca[Q[i]]][0] = min(lr[lca[Q[i]]][0], i);lr[lca[Q[i]]][1] = max(lr[lca[Q[i]]][1], i);}ans = 0;work(0);printf("%d\n", ans);for (int i = 1; i <= ans; i++) printf("%d ", sta[i] + 1);return 0; }
轉(zhuǎn)載于:https://www.cnblogs.com/L-Memory/p/7645705.html
總結(jié)
