2017.2.26 CF D2 402
这次状态还算能忍吧……一路不紧不慢切了前ABC（不紧不慢已经是在作死了），卡在D，然后跑去看E和F——卧槽怎么还有F，早知道前面做快点了……
F看了看，不会，弃
E看了看，不会，弃
D看了看，不会……没法再弃了。想了好久发现可以二分答案（浪费30min）
过了D以后去看F，发现果然还是不会（浪费20min）
之后看E，思路跑偏浪费20min+
此时时间还剩大约20min，终于想到了E可能是正解的做法，开始拼手速，各种调试，终于调过了样例，而时间只剩10s了……试图提交，拼手速成功，拼网速失败……
1000+分的差距，有时候只有几秒钟（其实是SX博主前面浪费太多时间，活该）
↑比赛结束后交了一发E，1A，这就更气了……
如果分数为x的学生数为奇数，那么无解。
否则把多于平均数量的学生给对面，累计答案
那个cnt似乎没必要
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
int a[mxn],b[mxn];
int cnt=;
int main(){
int i,j,x;
int n=read();
for(i=;i<=n;i++){
x=read();
a[x]++;
}
for(i=;i<=n;i++){
x=read();
b[x]++;
}
int ans=;
for(i=;i<=;i++){
if((a[i]+b[i])&){
printf("-1\n");
return ;
}
cnt+=(a[i]-(a[i]+b[i])/);
ans+=abs((a[i]-(a[i]+b[i])/));
}
if(cnt)printf("-1\n");
else{
printf("%d\n",ans/);
}
return ;
}
A
问至少删几个数字可以使得剩下的数能被10的k次方整除
暴力模拟，从尾部开始删。
注意特判只留一个0的情况。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
const int mxn=;
LL read(){
LL x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
LL n;int k;
int ans;
int main(){
int i,j;
n=read();k=read();
LL tmp=n;
int len=;
while(tmp){
tmp/=;
len++;
}
ans=len-;
tmp=n;
len=;
bool flag=;
while(tmp){
if(tmp%==)k--,flag=;
else len++;
if(!k)break;
tmp/=;
}
if(k)len=1e8;
if(k&&flag)ans++;
printf("%d\n",min(ans,len));
return ;
}
B
贪心？
现在至少买k件物品，剩下的在打折结束后买，问最小花费。
排个序，把现在买收益最大的至少k个买了，剩下的决策何时买
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
struct node{
int a,b,c;
}t[mxn];
int cmp(node x,node y){
return x.c<y.c;
}
int n,k;
int main(){
int i,j;
n=read();k=read();
for(i=;i<=n;i++){
t[i].a=read();
}
for(i=;i<=n;i++){
t[i].b=read();
t[i].c=t[i].a-t[i].b;
}
sort(t+,t+n+,cmp);
int ans=;
for(i=;i<=k;i++){
ans+=t[i].a;
}
for(i=k+;i<=n;i++){
ans+=min(t[i].a,t[i].b);
}
printf("%d\n",ans);
return ;
}
C
求最多的取字母次数使得剩下的串中包含目标串
二分取的次数……
我可能是思路太差……见二分答案的题老是看不出来。
花了好久才想起来二分答案，接着分分钟写完
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
int f[mxn];
char s[mxn],c[mxn];
int t[mxn];
int ls,lc;
bool solve(int lim){
int hd=;
for(int i=;i<=ls;i++){
if(t[i]<=lim)continue;
if(s[i]==c[hd])hd++;
if(hd>lc)return ;
}
return ;
}
int main(){
int i,j,x;
scanf("%s%s",s+,c+);
ls=strlen(s+);
lc=strlen(c+);
memset(f,0x3f,sizeof f);
f[]=0x3f3f3f3f;
for(i=;i<=ls;i++){
x=read();
t[x]=i;
}
int l=,r=ls,ans=;
while(l<=r){
int mid=(l+r)>>;
if(solve(mid)){
ans=mid;
l=mid+;
}
else r=mid-;
}
printf("%d\n",ans);
return ;
}
D
字符串处理稍有点麻烦，本质是个贪心问题。
刚开始思路完全跑偏了，写了各种递归，超复杂，半天调不对（估计对了也会T），浪费了半小时
后来发现每个式子中的变量在之前都已经出现了，并且式子中不会出现 [变量 运算 数字]的格式（根本没有好好读题嘛）
@NOI2014 T1 起床困难综合征
把“?”看作第一个出现的变量，依次确定每一位是0还是1←暴力从前到后所有的式子，在"?"确定的情况下后面的变量都能被依次算出来，看"?"的这一位取0还是1可以使得结果中1最多（答案最大）。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
struct edge{
int v,nxt,op;
}e[mxn<<];
int hd[mxn],mct=;
void add_edge(int u,int v,int op){
e[++mct].v=v;e[mct].nxt=hd[u];e[mct].op=op;hd[u]=mct;return;
}
//
struct node{
string num;
int p1,p2;
int op;
}t[]; //
int f[][];
int pre[];
int op[];
map<string,int>mp;
int cnt=;
int n,m;
string s;
string cut(int st){
string tmp;tmp.clear();
int len=s.size();
for(int i=st;i<len;i++){
if(s[i]==' ')break;
tmp+=s[i];
}
return tmp;
}
int tst(int id){
int res=;
// printf("id:%d f1:%d\n",id,f[1][id]);
for(int i=;i<=cnt;i++){
// printf("i:%d op:%d p1:%d p2:%d\n",i,t[i].op,t[i].p1,t[i].p2);
if(t[i].op==-){
// printf("num:%d\n",f[i][id]);
}
else{
if(t[i].op==){
f[i][id]=f[t[i].p1][id]|f[t[i].p2][id];
}
if(t[i].op==){
f[i][id]=f[t[i].p1][id]^f[t[i].p2][id];
}
if(t[i].op==){
f[i][id]=f[t[i].p1][id]&f[t[i].p2][id];
}
}
// printf(" %d\n",f[i][id]);
if(f[i][id]==)res++;
}
// printf("res:%d\n",res);
return res;
}
int minif[],mxf[];
int main(){
int i,j;
n=read();m=read();
memset(op,-,sizeof op);
mp["?"]=++cnt;
for(i=;i<=n;i++){
getline(cin,s);
// cout<<s<<endl;
int st=,len=s.length();
//
string c=cut(st);
// cout<<c<<endl;
if(!mp[c])mp[c]=++cnt;
st+=c.length()+;
string tmp=cut(st);
// cout<<tmp<<endl;
st+=tmp.length()+;
// if(s.find("XOR")!=string::npos){//
t[mp[c]].op=;
string c1=cut(st);
st+=c1.length()+;
st+=;
string c2=cut(st);
t[mp[c]].p1=mp[c1];
t[mp[c]].p2=mp[c2];
}
else if(s.find("OR")!=string::npos){//
t[mp[c]].op=;
string c1=cut(st);
// cout<<c1<<endl;
st+=c1.length()+;
st+=;
string c2=cut(st);
t[mp[c]].p1=mp[c1];
t[mp[c]].p2=mp[c2];
}
else if(s.find("AND")!=string::npos){//
t[mp[c]].op=;
string c1=cut(st);
st+=c1.length()+;
st+=;
string c2=cut(st);
t[mp[c]].p1=mp[c1];
t[mp[c]].p2=mp[c2];
}
else if(s.find("") || s.find("")){
t[mp[c]].op=-;
string c1=cut(st);
// cout<<c1<<endl;
t[mp[c]].num=c1;
int len=c1.length();int v=mp[c];
for(j=;j<len;j++){
f[v][j]=c1[len-j-]-'';
}
}
} for(i=;i<m;i++){
f[][i]=;
int t1=tst(i);
f[][i]=;
int t2=tst(i);
if(t1<t2){
minif[i]=;
mxf[i]=;
}
else if(t1==t2){
minif[i]=;
mxf[i]=;
}
else{
minif[i]=;
mxf[i]=;
}
}
for(i=m-;i>=;i--)printf("%d",minif[i]);
printf("\n");
for(i=m-;i>=;i--)printf("%d",mxf[i]);
return ;
}
E
差1分钟就能进rank100了，那叫一个气
这个时候只有我的过气女团能安慰我了