T1.exercise
题解
数据很小直接模拟
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m;
int a[2005];
int main()
{
freopen("exercise.in","r",stdin);
freopen("exercise.out","w",stdout);
for(int i=1;i<=1440;i++)a[i]=1;
n=read();m=read();
for(int i=1;i<=m;i++)
{
char ch[25];
scanf("%s",ch);
int l=read(),r=read(),v=read();
for(int j=l;j<=r;j++)a[j]-=v;
}
int sum=n;
for(int i=1;i<=1440;i++)
{
sum+=a[i];
if(sum<=0){printf("Runtime Error\n%d\n",i);return 0;}
}
puts("Accepted");
printf("%d",sum);
return 0;
}
T2.catclimb
题解
迭代深搜，最好先排个序。。。
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool flag;
int n,w,deep,sum;
int c[20],b[20];
void dfs(int x)
{
if(x==n+1){flag=1;return;}
for(int i=1;i<=deep;i++)
if(b[i]+c[x]<=w)
{
b[i]+=c[x];
dfs(x+1);
b[i]-=c[x];
if(flag)return;
}
return;
}
int main()
{
freopen("catclimb.in","r",stdin);
freopen("catclimb.out","w",stdout);
n=read();w=read();
for(int i=1;i<=n;i++)c[i]=read(),sum+=c[i];
sort(c+1,c+n+1,greater<int>());
for(deep=sum/w;deep<=18;deep++)
{
dfs(1);
if(flag)
{
printf("%d\n",deep);
return 0;
}
}
return 0;
}
T3.war
题解
部分分快排。。
正解平衡树
AC代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int tmp;
int n,m,root,size;
int b[300005],v[300005],w[300005],s[300005],rnd[300005];
int ls[300005],rs[300005];
bool tag[300005];
void update(int k){s[k]=s[ls[k]]+s[rs[k]]+w[k];}
void rturn(int &k)
{int t=ls[k];ls[k]=rs[t];rs[t]=k;update(k);update(t);k=t;}
void lturn(int &k)
{int t=rs[k];rs[k]=ls[t];ls[t]=k;update(k);update(t);k=t;}
void insert(int &k,int num)
{
if(!k){k=++size;rnd[k]=rand();w[k]=s[k]=1;v[k]=num;return;}
s[k]++;
if(num==v[k]){w[k]++;return;}
else if(num<v[k]){insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);}
else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);}
}
void del(int &k,int num)
{
if(!k)return;
if(num==v[k])
{
if(w[k]>1){w[k]--;s[k]--;return;}
if(ls[k]*rs[k]==0)k=ls[k]+rs[k];
else if(rnd[ls[k]]<rnd[rs[k]]){rturn(k);del(k,num);}
else {lturn(k);del(k,num);}
}
else if(num<v[k])
{del(ls[k],num);s[k]--;}
else {del(rs[k],num);s[k]--;}
}
int query(int k,int x)
{
if(!k)return -1;
if(s[ls[k]]>=x)return query(ls[k],x);
else if(x>s[ls[k]]+w[k])return query(rs[k],x-w[k]-s[ls[k]]);
else return k;
}
int main()
{
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)b[i]=read();
for(int i=1;i<=n;i++)insert(root,b[i]);
m=read();
int k,x;
for(int i=1;i<=m;i++)
{
char ch[2];
scanf("%s",ch);
if(ch[0]=='A')
{
k=read();x=read();
del(root,b[k]);b[k]-=x;
if(b[k]>0)insert(root,b[k]);
else n--;
}
else if(ch[0]=='C')
{
k=read();x=read();
del(root,b[k]);b[k]+=x;
insert(root,b[k]);
}
else
{
k=read();
if(k>n)puts("-1");
else printf("%d\n",v[query(root,n-k+1)]);
}
}
printf("%d\n",n);
return 0;
}