传送门：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();
}
}
