多模室内设计网站/自动点击器

1038A. Equality 水

给定只由前k个小写字母组成的字符串s，s的好子序列要求里面k个字母的数量都相同，求最大的好子序列长度。

前k个字母最小的数量*k

1038B. Non-Coprime Partition 构造

把前n个正整数分成两个非空集合使得它们和的gcd不为1，输出方案。

构造题，先想无解情况，前n个正整数的和为n(n+1)/2,所以一定是n/2或(n+1)/2的整数倍（取决于哪个是整数），当n=1或2时无解，其余情况都有解。

1038C. Gambling 贪心

两个人轮流操作，每个人手里有一堆牌，每次要么移除对方手里一张牌，要么移除自己手里一张牌并获得牌上数字的得分。两个人都绝顶聪明且要使得自己的分-对方的分最大，求最后两个人的分差。

每次总是操作当前场上最大的牌，是自己的就加上，是对方的就移除。排序后模拟这个过程即可。

1038D. Slime 结论

n(5e5)个史莱姆排成一排，每个史莱姆都有一个分数（可以为负），史莱姆可以吃掉相邻的史莱姆，然后他的积分变成x-y, x是它原来的分数，y是被吃掉的史莱姆的分数。求最后只剩下一个史莱姆时它最大的积分。

相当于给数字或相反数求和，要求至少有一个数字变为相反数（除n=1外，n=1直接输出原值），且不能全部变为相反数。
如果数字全为正，那么选择最小的一个变反。
如果数字全为负，那么选择最大的一个不变反。
如果数字有正有负，那么输出绝对值的和即可。

int main(void)
{int n(read()), mi(INT_MAX), ma(INT_MIN);ll sum = 0;for(int i(1);i<=n;++i){int t(read());sum += abs(t);mi = min(mi,t);ma = max(ma,t);}if(mi>0) sum -= 2*mi;else if(ma<0) sum += 2*ma;printf("%I64d\n",n>1?sum:mi );return 0;
}

这样的写法比原来的写法简洁了几十倍，但是要考虑好边界情况比如n=1时。

1038E. Maximum Matching 图论，dp，分类

4个点，100条边（有自环重边），边有权值，求最大权值和的路，输出权值和。

方法一：分类讨论+分类讨论+分类讨论

我最开始的方法，一个多小时没分类完。

方法二：暴力dp

参考 twinkle_ 的代码

状态表示：$dp[i][j][x][y]$，其中ij是边的编号，xy是节点编号，dp表示使用i到j内的部分边,从x走到y的最大权值和。
初始状态：$dp[i][i][x][y] = dp[i][i][y][x] = v（第i条边连接x,y，权值为v）$
状态转移：

$$dp[i][j][x][y] = max_{k=i}^{j-1}\{dp[i][k][x][y],dp[k+1][j][x][y],max_{t=1}^4\{dp[i][k][x][t]+dp[k+1][j][t][y],dp[i][k][t][y]+dp[k+1][j][x][t]\}\}$$
复杂度：状态数 $100*100*4*4$,状态转移 $100*4$,总复杂度大约6e7。

这样写好爽啊

ll dp[N][N][5][5];
int main(void)
{int n = read();memset(dp,0xc0,sizeof(dp));for(int i=1;i<=n;i++){int x = read(), v = read(), y = read();dp[i][i][x][y] = dp[i][i][y][x] = v;}ll ans = 0;for(int i=n;i>=1;--i) for(int j=i;j<=n;++j) for(int x=1;x<=4;++x) for(int y=1;y<=4;++y){ll &res = dp[i][j][x][y];for(int k = i; k<=j+1; ++k){res = max(res,max(dp[i][k][x][y],dp[k+1][j][x][y]));for(int t=1;t<=4;++t){res = max(res,dp[i][k][x][t]+dp[k+1][j][t][y]);res = max(res,dp[i][k][t][y]+dp[k+1][j][x][t]);}}ans = max(ans,res);}printf("%I64d\n",ans );return 0;
}

方法三：图论

题目可以理解为求一条权值最大的欧拉路。当小于四点联通时，一定有欧拉路，当四点连通时，有：

无向图存在欧拉路的条件
所有点度都是偶数，或者恰好有两个点度是奇数，则有欧拉路。若有奇数点度，则奇数点度点一定是欧拉路的起点和终点，否则可取任意一点作为起点。

如果以上条件满足，将所有边权相加即可。
如果不满足，则考虑拆掉最小的一条边，且这条边不能是桥。
除此之外，也须考虑不全部用到四个点的情况。

算法：
如果图四连通且有欧拉路，答案就是所有边之和。
否则，求所有可能的一连通，二连通，三连通的答案，并求4连通总和删去最小的非桥边的答案，取最大值。

并查集查询时记得要再做一次getfa()，求桥可以使用更快的tarjan算法。

class UnionFindSet
{int n;vector<int> fa;
public:UnionFindSet(int _n) : n(_n){fa = vector<int>(n+1);for(int i=1;i<=n;i++)fa[i] = i;}void mesh(int x, int y){x = getfa(x), y = getfa(y);if(x != y)fa[x] = fa[y] = min(x,y);}int getfa(int p){return fa[p]==p ? fa[p] : fa[p]=getfa(fa[p]);}bool connect(){for(int i=1;i<=n;i++)if(getfa(i)!=1)return false;return true;}
};
struct Edge
{int sum;int min = INT_MAX;int num;
}edge[5][5];
int get()
{int ret = INT_MAX;for(int i=1;i<=4;i++) for(int j=i+1;j<=4;j++) if(edge[i][j].num){if(edge[i][j].num>=2)ret = min(ret,edge[i][j].min);else if(edge[i][j].num==1){UnionFindSet ufs(4);for(int ti=1;ti<=4;ti++) for(int tj=ti+1;tj<=4;tj++) if(ti!=i||tj!=j){if(edge[ti][tj].num)ufs.mesh(ti,tj);}if(ufs.connect()) //不是桥ret = min(ret,edge[i][j].min);}}return ret==INT_MAX?-1:ret;
}
int deg[5];int main(void)
{int n = read();int ans = 0;UnionFindSet all(4);for(int i=1;i<=n;i++){int x = read(), v=read(), y=read();if(x>y) swap(x,y);edge[x][y].sum+=v;edge[x][y].num++;edge[x][y].min = min(edge[x][y].min,v);deg[x]++, deg[y]++;all.mesh(x,y);}//单连通for(int i=1;i<=4;i++)ans = max(ans, edge[i][i].sum);//二连通const int mp2[6][2] = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}};for(int k=0;k<6;k++){int a = mp2[k][0], b = mp2[k][1];if(edge[a][b].num)ans = max(ans, edge[a][a].sum + edge[a][b].sum + edge[b][b].sum);}//三连通const int mp3[4][3] = {{1,2,3},{1,2,4},{1,3,4},{2,3,4}};for(int k=0;k<4;k++){int check = 0;for(int i=0;i<3;i++)for(int j=i+1;j<3;j++)check += edge[mp3[k][i]][mp3[k][j]].num > 0;if(check >= 2){int tmp = 0;for(int i=0;i<3;i++)for(int j=i;j<3;j++)tmp += edge[mp3[k][i]][mp3[k][j]].sum;ans = max(ans,tmp);}}//四连通if(all.connect()){int check = 0;for(int i=1;i<=4;i++)if(deg[i]&1) check++;int tmp = 0;for(int i=1;i<=4;i++)for(int j=i;j<=4;j++)tmp += edge[i][j].sum;if(check!=4) //全部可用!ans = tmp;else //删去最小的非桥{int subs = get();if(subs!=-1)ans = max(ans,tmp-subs);}}printf("%d\n",ans );return 0;
}