传送门：AtCoder Regular Contest 164 - AtCoder

A.签到题，在此不做赘述

B - Switching Travel

这题本来该是秒的，但是因为没有考虑清楚环的问题而被卡半天，其实我们不难发现，要想使题目存在节点，就得让该节点出现一条环同时，而且环最后的头和尾颜色还必须得相等。直接dfs跑环加暴力枚举即可。

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,m;
int id;
int ue[1000005];
void icealsoheat(){cin>>n>>m;vector<vector<int>>ve(n+5);for(int i=1;i<=m;i++){int l,r;cin>>l>>r;ve[l].push_back(r);ve[r].push_back(l);}vector<int>c(n+5,0);for(int i=1;i<=n;i++)cin>>ue[i];bool f=0;id=0;auto dfs=[&](auto self,int x,int fa)->void{for(auto i:ve[x]){if(c[i]||ue[i]==ue[x])continue;c[i]=id;self(self,i,x);}};for(int i=1;i<=n;i++){if(c[i]==0){id++;c[i]=id;dfs(dfs,i,-1);}for(auto j:ve[i]){if(ue[i]==ue[j]&&c[i]==c[j])f=1;}        if(f)break;}// for(int i=1;i<=n;i++)cout<<c[i]<<"+++\n";// cout<<c[4]<<"----\n";if(f)puts("Yes");else puts("No");}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;// cin>>_;while(_--){icealsoheat();}
}

C - Reversible Card Game

通过贪心的思想，双方若想都取最优，爱丽丝尽可能把差值大的值的从大的翻到小的，而鲍勃尽可能的在爱丽丝得手之前把没翻的牌（差值尽可能大的）拿走。然后，当正面大的牌都拿完的时候，鲍勃只需跟着爱丽丝拿，爱丽丝翻一张（把大的值翻上来），鲍勃就拿一张。

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,m;
int a[1000005];
int b[1000005];
bool c[1000005];
struct we{int x;int cha;bool operator <(const we &k)const{return k.cha>cha;}
};
bool cmp(we ae,we be){return ae.cha<be.cha;
}
void icealsoheat(){cin>>n;priority_queue<we>q;vector<we>ve;priority_queue<we>qq;int ans=0;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];ans+=min(a[i],b[i]);if(a[i]>b[i]){q.push({i,abs(a[i]-b[i])});}else{ve.push_back({i,abs(a[i]-b[i])});}}int op=0;while(q.size()){we now=q.top();q.pop();if(op==0){op^=1;ve.push_back({now});}if(!q.size())break;now=q.top();q.pop();if(op==1){op^=1;ans+=now.cha;}}// cout<<ans<<"+++\n";sort(ve.begin(),ve.end(),cmp);for(auto [i,j]:ve){if(op==0){ans+=j;}else op^=1;}cout<<ans;
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;// cin>>_;while(_--){icealsoheat();}
}

D - 1D Coulomb

一道很经典很妙的dp。

我们需要用dp迭代一下类似括号匹配的一样的结构。让+与-相互抵消。

dp[i][j]为值的和，i代表了前i个字母，j代表着+与-的差值状态。（n为+与-相等，0到n-1是-的较多，n+1到2*n是+较多）。hh[i][j]为当前方案的次数。

代码如下：

//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
int n,m,k;
void icealsoheat(){cin>>n;string s;cin>>s;s=' '+s;vector<vector<int>>dp(2*n+5,vector<int>(2*n+5,0));vector<vector<int>>hh(2*n+5,vector<int>(2*n+5,0));hh[0][n]=1;for(int i=1;i<=2*n;i++){for(int j=0;j<=2*n;j++){if(s[i]=='+'||s[i]=='?'){if(j>0){dp[i][j]=(dp[i][j]+dp[i-1][j-1])%N;hh[i][j]=(hh[i][j]+hh[i-1][j-1])%N;}if(j<=n&&j>0){int v=n-j;v=v*2+1;dp[i][j]=(dp[i][j]+hh[i-1][j-1]*v%N)%N;}}if(s[i]=='-'||s[i]=='?'){if(j<2*n){dp[i][j]=(dp[i][j]+dp[i-1][j+1])%N;hh[i][j]=(hh[i][j]+hh[i-1][j+1])%N;}if(j>=n&&j<2*n){int v=j-n;v=v*2+1;dp[i][j]=(dp[i][j]+hh[i-1][j+1]*v%N)%N;                    }}}}cout<<dp[2*n][n];}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;// cin>>_;while(_--){icealsoheat();}
}