Codeforces Round #499 (Div. 2)
https://codeforces.com/contest/1011
A
#include <bits/stdc++.h>
using namespace std;
int n,k,i,j,p,r,a[];
string s;
int main(){
for(cin>>n>>k>>s;i<n;i++)a[i]=s[i]-'a'+;
sort(a,a+n);
for(i=,p=-;i<n&&j<k;i++){
if(p+<a[i])r+=a[i],j++,p=a[i];
}
cout<<(j==k?r:-);
}
B
#include <bits/stdc++.h>
using namespace std;
int n,m,k,i,x,t,l,r,c[];
int main(){
for(cin>>n>>m;i<m;i++)cin>>x,c[x]++;
for(l=,r=;(l+r)/>l;){
k=(l+r)/;
for(t=i=;i<;i++)t+=c[i]/k;
(t>=n?l:r)=k;
}
cout<<l;
}
C
模拟
题意：从地球飞到火星要经过n-2个星球，最后直接返回地球，每次起飞和降落都需要燃料，且效率不同。火箭重为m，星球数为n，火箭在星球上起飞和降落时的燃料效率ai和bi，求出发时需携带的最小燃料量，若不可行，输出-1。
思路：直接模拟即可
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define IT set<node>::iterator
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 200005
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int> pli;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
const double oula=0.57721566490153286060651209;
using namespace std; int a[],b[]; int main(){
// std::ios::sync_with_stdio(false);
int n;
double s;
cin>>n>>s;
int flag=;
for(int i=;i<=n;i++){
cin>>a[i];
if(a[i]<=){
flag=;
}
}
for(int i=;i<=n;i++){
cin>>b[i];
if(b[i]<=){
flag=;
}
}
if(!flag){
cout<<-;
}
else{
double ans=;
for(int i=;i<=n;i++){
double tmp;
tmp=s/(a[i]-);
s+=tmp;
ans+=tmp;
tmp=s/(b[i]-);
s+=tmp;
ans+=tmp;
}
printf("%.7f\n",ans);
}
}
D
交互题
题意：系统想一个数，你来猜，猜的数比系统想的大，返回1，小则返回-1，猜对了返回0。特殊的是，该系统每隔k次询问会撒一次谎，输出猜对的过程（猜的次数不超过60）
思路：前k次询问先找到系统第一次说谎的时候，剩下的60-k次就二分猜就行
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define IT set<node>::iterator
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 200005
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int> pli;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
const double oula=0.57721566490153286060651209;
using namespace std; int a[]; int main(){
std::ios::sync_with_stdio(false);
int n,m;
cin>>m>>n;
int x;
for(int i=;i<n;i++){
cout<<<<endl;
cin>>x;
if(x==) return ;
a[i]=x;
}
int L=,R=m,mid;
for(int i=n;i<;i++){
mid=L+R>>;
cout<<mid<<endl;
cin>>x;
if(x==) return ;
if(x*a[i%n]>){
L=mid+;
}
else{
R=mid-;
}
}
}
E
题意：有n种价值不同的钞票，每种有无数张。问在k进制下能凑出几种尾数不同的钞票
思路：gcd求最大公约数即可
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define IT set<node>::iterator
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 200005
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int> pli;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
const double oula=0.57721566490153286060651209;
using namespace std; int main(){
std::ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
int a;
cin>>a;
int gcd=a;
for(int i=;i<=n;i++){
cin>>a;
gcd=__gcd(gcd,a);
if(gcd==) break;
}
gcd=__gcd(gcd,k);
int ans=k/gcd;
cout<<ans<<endl;
for(int i=;i<ans;i++){
cout<<gcd*i<<" ";
}
}
F
思维题
题意：给你一颗二叉树，父节点的值等于子节点的值通过“四则运算”得到（XOR，OR，AND，NOT）,问每次改变一个叶子节点的值后，根节点的值为多少，每个操作之间互不影响
思路：先跑一遍dfs，求出根结点的值，第二次遍历的时候分类讨论，判断一个节点的值的改变对其父节点有没有影响。
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define IT set<node>::iterator
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int> pli;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
const double oula=0.57721566490153286060651209;
using namespace std; vector<int>ve[maxn];
int n;
struct sair{
string str;
int v;
}a[maxn]; int val[maxn];
int ans[maxn];
int vis[maxn]; void dfs1(int pos){
int ans;
if(a[pos].str=="AND"){
for(int i=;i<ve[pos].size();i++){
dfs1(ve[pos][i]);
}
val[pos]=val[ve[pos][]]&val[ve[pos][]];
}
else if(a[pos].str=="IN"){
val[pos]=a[pos].v;
}
else if(a[pos].str=="XOR"){
for(int i=;i<ve[pos].size();i++){
dfs1(ve[pos][i]);
}
val[pos]=val[ve[pos][]]^val[ve[pos][]];
}
else if(a[pos].str=="NOT"){
dfs1(ve[pos][]);
val[pos]=!val[ve[pos][]];
}
else{
for(int i=;i<ve[pos].size();i++){
dfs1(ve[pos][i]);
}
val[pos]=val[ve[pos][]]|val[ve[pos][]];
}
} void dfs2(int pos){
int x,y;
// cout<<pos<<endl;
if(a[pos].str=="IN"){
ans[pos]=!val[];
}
else if(a[pos].str=="AND"){
x=val[ve[pos][]],y=val[ve[pos][]];
if(x==&&y==){
dfs2(ve[pos][]);
}
else if(x==&&y==){
dfs2(ve[pos][]);
}
else if(x==&&y==){
dfs2(ve[pos][]);
dfs2(ve[pos][]);
}
}
else if(a[pos].str=="OR"){
x=val[ve[pos][]],y=val[ve[pos][]];
if(x==&&y==){
dfs2(ve[pos][]);
}
else if(x==&&y==){
dfs2(ve[pos][]);
}
else if(x==&&y==){
dfs2(ve[pos][]);
dfs2(ve[pos][]);
}
}
else if(a[pos].str=="XOR"){
x=val[ve[pos][]],y=val[ve[pos][]];
if(x==&&y==){
dfs2(ve[pos][]);
dfs2(ve[pos][]);
}
else if(x==&&y==){
dfs2(ve[pos][]);
dfs2(ve[pos][]);
}
else if(x==&&y==){
dfs2(ve[pos][]);
dfs2(ve[pos][]);
}
else if(x==&&y==){
dfs2(ve[pos][]);
dfs2(ve[pos][]);
}
}
else if(a[pos].str=="NOT"){
x=val[ve[pos][]];
dfs2(ve[pos][]);
}
} int main(){
std::ios::sync_with_stdio(false);
cin>>n;
string str;
int x,y;
for(int i=;i<=n;i++){
cin>>str>>x;
a[i].str=str;
if(str=="AND"){
cin>>y;
ve[i].pb(x);
ve[i].pb(y);
a[i].v=;
}
else if(str=="IN"){
a[i].v=x;
}
else if(str=="XOR"){
cin>>y;
ve[i].pb(x);
ve[i].pb(y);
a[i].v=;
}
else if(str=="NOT"){
ve[i].pb(x);
a[i].v=;
}
else{
cin>>y;
ve[i].pb(x);
ve[i].pb(y);
a[i].v=;
}
}
dfs1();
for(int i=;i<=n;i++) ans[i]=val[];
dfs2();
for(int i=;i<=n;i++){
if(a[i].str=="IN"){
cout<<ans[i];
}
}
cout<<endl;
}