目录
E. Reachability from the Capital
依照题目意思左右遍历标记即可
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 ;
}按照题目意思倒着来即可
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 ;
}
我们可以优先把每一个字母的下标存下来然后判断有没有同时标记即可(倒着存就可以正着求前面的了)
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 ;
}
我们可以灵巧使用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 ;
}有向图的连接我们考虑使用缩点的方式来解决问题缩点然后重新建图然后看没有入度的点的数量就是答案
#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;
}我们可以发现有贡献的只有对于喜欢同一种类型的人的分配方式，对于这样一个问题我们可以定义状态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 ;
}
更多【算法-Codeforces Round 490 (Div. 3)】相关视频教程：www.yxfzedu.com