目錄

A. Mishka and Contest

B. Reversing Encryption

C. Alphabetic Removals

D. Equalize the Remainders

E. Reachability from the Capital

F. Cards and Joy

---

A. Mishka and Contest

依照題目意思左右遍歷標記即可

void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int i=1;i<=n;i++){if(st[i] || a[i]>m) break; ans++;st[i]=true;}for(int i=n;i>=1;i--){if(st[i] || a[i]>m) break; ans++;st[i]=true;}cout<<ans<<endl;return ;
}

B. Reversing Encryption

按照題目意思倒著來即可

void solve(){cin>>n;string s; cin>>s; s=' '+s;for(int i=1;i<=n;i++){if(n%i==0){for(int l=1,r=i;l<=r;l++,r--) swap(s[l],s[r]);}}for(int i=1;i<=n;i++) cout<<s[i];cout<<endl;return ;
}

C. Alphabetic Removals

我們可以優先把每一個字母的下標存下來然后判斷有沒有同時標記即可(倒著存就可以正著求前面的了)

void solve(){cin>>n>>m;string s; cin>>s; s=' '+s;vector<vector<int>> ton(26);for(int i=n;i>=1;i--){ton[s[i]-'a'].push_back(i);}vector<bool> st(n+5);while(m--){for(int i=0;i<26;i++){if(!ton[i].empty()){st[ton[i].back()]=true;ton[i].pop_back();break;}}}for(int i=1;i<=n;i++) if(!st[i]) cout<<s[i];cout<<endl;return ;
}

D. Equalize the Remainders

我們可以靈巧使用set來解決問題，為什么這樣思考呢？我們肯定十一次性對當前這個數%m的值直接變到應該變化的位置是最好的可以用set來存儲還沒有抵達的位置然后直接變化過去即可這樣就是nlog級別的

void solve(){cin>>n>>m;vector<int> cnt(m),a(n+1);int num=n/m;set<int> S;for(int i=0;i<m;i++) S.insert(i);LL ans=0;for(int i=1;i<=n;i++){cin>>a[i];int t=*S.rbegin();int v=a[i]%m;if(v>t) t=*S.begin();else t=*S.lower_bound(v);if(++cnt[t]==num) S.erase(t);a[i]+=(t-v+m)%m;ans+=(t-v+m)%m;}cout<<ans<<endl;for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;return ;
}

E. Reachability from the Capital

有向圖的連接我們考慮使用縮點的方式來解決問題縮點然后重新建圖然后看沒有入度的點的數量就是答案

#include <bits/stdc++.h>
using namespace std;
const int N = 50010;int n,m,S;vector<int> g[N];int dfn[N],low[N],stk[N],top,timetamp,scc_cnt;
bool is_stk[N];
int id[N],din[N];
void tarjan(int u){dfn[u]=low[u]=++timetamp;stk[++top]=u,is_stk[u]=true;for(auto&v:g[u]){if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(is_stk[v]) low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){++scc_cnt;int y;do{y=stk[top--];is_stk[y]=false;id[y]=scc_cnt;}while(y!=u);}
}
int main(){cin>>n>>m>>S;while(m--){int a,b; cin>>a>>b;g[a].push_back(b);}for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);for(int i=1;i<=n;i++){for(auto &v:g[i]){int a=id[i],b=id[v];if(a!=b){din[b]++;}}}int sum=0;din[id[S]]++;for(int i=1;i<=scc_cnt;i++){if(!din[i]) sum++;}cout<<sum<<endl;return 0;
}

F. Cards and Joy

我們可以發現有貢獻的只有對于喜歡同一種類型的人的分配方式，對于這樣一個問題我們可以定義狀態dp[i][j]i個人分j張牌的最大喜歡值是多少可以由i-1分min(0,j-m)-j轉移過來即可

// Problem: F. Cards and Joy
// Contest: Codeforces - Codeforces Round 490 (Div. 3)
// URL: https://codeforces.com/contest/999/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define LF(x)   fixed<<setprecision(x)// c++ 保留小數
#define int long long
typedef long long LL;
typedef unsigned long long ULL;
typedef tuple<int,int,int> TUP;
typedef pair<int, int> PII;
const int N=1000010,M=1010,INF=0x3f3f3f3f,pp=13331,mod=1e9+7;
const double pai=acos(-1.0);// pai
int t,n,m,k;
int ton[N];
int num[N];
int w[N];void solve()
{// 有個明顯的結論就是我們只有 喜歡同一種類型牌的選手互相最優分配即可// 不同之間沒有影響// 對于每一種牌的類型  假設數量為 sum  我們要分給m個人 最多 k張 如果一個人分到的是 [1-k] 權重也是不一樣的// 不妨定義為 dp[i][j][sum]// 表示i個人分到j張的最優解是多少同時以及已經分了sum的條件下cin>>n>>m;for(int i=1;i<=n*m;i++){int x; cin>>x;ton[x]++;}    set<int> S;for(int i=1;i<=n;i++){int x; cin>>x;num[x]++;// 喜歡同一個數字的人數S.insert(x);}for(int i=1;i<=m;i++) cin>>w[i];int ans=0;for(auto&v:S){// 對于 同一種類型的牌vector<vector<int>> dp(num[v]+5,vector<int>(ton[v]+5,-INF));dp[0][0]=0;for(int i=1;i<=num[v];i++)for(int j=0;j<=ton[v];j++)for(int k=max(0ll,j-m);k<=j;k++){dp[i][j]=max(dp[i][j],dp[i-1][k]+w[j-k]);}int res=0;for(int i=0;i<=ton[v];i++) res=max(res,dp[num[v]][i]);ans+=res;}cout<<ans<<endl;return ;
}