Codeforces_841
2024-09-03 05:11:38
A.统计每个字母数量,比较是否超过k。
#include<bits/stdc++.h>
using namespace std; int n,k,cnt[] = {};
string s; int main()
{
ios::sync_with_stdio();
cin >> n >> k >> s;
for(int i = ;i < s.length();i++) cnt[s[i]-'a']++;
for(int i = ;i < ;i++)
{
if(cnt[i] > k)
{
cout << "NO" << endl;
return ;
}
}
cout << "YES" << endl;
return ;
}
B.只要有奇数,First必赢,因为总能到奇数个数为奇数个的情况。
#include<bits/stdc++.h>
using namespace std; int n,a[]; int main()
{
ios::sync_with_stdio();
cin >> n;
int cnt = ;
for(int i = ;i <= n;i++)
{
cin >> a[i];
if(a[i]%) cnt++;
}
if(cnt > ) cout << "First" << endl;
else cout << "Second" << endl;
return ;
}
C.当在[1,x]中随机取一个的时候,最小值期望为x/2,取的次数越多,期望越小。我们把优先次数少的分给大的数。
#include<bits/stdc++.h>
using namespace std; int n,a[],ans[];
struct xx
{
int x,id;
friend bool operator <(xx a,xx b)
{
return a.x > b.x;
}
}b[]; int main()
{
ios::sync_with_stdio();
cin >> n;
for(int i = ;i <= n;i++) cin >> a[i];
for(int i = ;i <= n;i++)
{
cin >> b[i].x;
b[i].id = i;
}
sort(a+,a++n);
sort(b+,b++n);
for(int i = ;i <= n;i++) ans[b[i].id] = a[i];
for(int i = ;i <= n;i++) cout << ans[i] << " ";
cout << endl;
return ;
}
D.首先图是连通的,若有-1的点存在,则必可以通过这个点,dfs把其它点都调整好。
若没有-1的点存在,我们随便选一个点,dfs下去,最后判断这个点是否符合。
#include<bits/stdc++.h>
using namespace std; int n,m,a[],vis[] = {},dep[] = {};
struct xxx
{
int to,id;
xxx(int a,int b):to(a),id(b){};
};
vector<xxx> v[];
vector<int> ans; bool dfs(int now,int pre)
{
vis[now] = ;
for(int i = ;i < v[now].size();i++)
{
int t = v[now][i].to;
if(t == pre || vis[t]) continue;
if(dfs(t,now))
{
dep[now]++;
ans.push_back(v[now][i].id);
}
}
if(a[now] == && dep[now]% == || a[now] == && dep[now]% == ) return ;
return ;
} int main()
{
ios::sync_with_stdio();
cin >> n >> m;
for(int i = ;i <= n;i++) cin >> a[i];
for(int i = ;i <= m;i++)
{
int x,y;
cin >> x >> y;
v[x].push_back(xxx(y,i));
v[y].push_back(xxx(x,i));
}
int ok = ;
for(int i = ;i <= n;i++)
{
if(a[i] == -)
{
dfs(i,);
ok = ;
break;
}
}
if(!ok && dfs(,))
{
cout << - << endl;
return ;
}
cout << ans.size() << endl;
for(int i = ;i < ans.size();i++) cout << ans[i] << " ";
cout << endl;
return ;
}
最新文章
- nginx的pass_proxy遇到的坑
- ASP.NET发送邮件(QQ发送)
- 【Python排序搜索基本算法】之深度优先搜索、广度优先搜索、拓扑排序、强联通&;Kosaraju算法
- Dapper使用在WCF上总是说Service找不到
- 使用OpenXml把Excel中的数据导出到DataSet中
- [css]display: table-cell,用div做分列布局
- javascript数组的常用算法解析
- Spring Cloud微服务实战:手把手带你整合eureka&;zuul&;feign&;hystrix
- Centos7 安装 tree
- 【FJOI 20170305】省选模拟赛
- 可由inetd启动的协议无关时间获取服务器程序
- 修复服务器上出现ImportError: cannot import name main的问题
- 关于java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to 实体类
- [Codeforces 1016F]Road Projects
- ASP.NET Core奇遇记:无用户访问,CPU却一直100%
- PAT1135(红黑书的判定)
- AngularJs中url参数的获取
- bootstrap2.1相关文档
- php计算两个日期时间差(返回年、月、日)
- free 释放内存