# AGC011 题解()-其他

## AGC011 题解()

### [AGC011A] Airport Bus

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,c,k,ans,a[100010];
int main(){
scanf("%d%d%d",&n,&c,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
int cnt=0,t=0;
for(int i=1;i<=n;i++){
if(cnt>=c||a[i]>t)t=a[i]+k,cnt=1,ans++;
else cnt++;
}
printf("%d\n",ans);
return 0;
}


### [AGC011B] Colorful Creatures

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n,ans,a[100010];
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(a[i+1]<=2*a[i])ans++;
else ans=0;
a[i+1]+=a[i];
}
printf("%lld\n",ans);
return 0;
}


### [AGC011C] Squared Graph

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a,b,c,col[100010];
struct node{
int v,next;
}edge[400010];
void add(int u,int v){
}
bool dfs(int x,int c){
col[x]=c;
bool jud=true;
if(col[edge[i].v]){
if(col[edge[i].v]==col[x])jud=false;
}
else jud&=dfs(edge[i].v,3-c);
}
return jud;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
}
for(int i=1;i<=n;i++){
if(col[i])continue;
else{
if(dfs(i,1))b++;
else a++;
}
}
long long ans=0;
int cnt=0;
for(int i=1;i<=a;i++)ans+=2*cnt+1,cnt++;
for(int i=1;i<=b;i++)ans+=2*cnt+2,cnt+=2;
cnt=n-c;
for(int i=1;i<=c;i++)ans+=2*cnt+1,cnt++;
printf("%lld\n",ans);
return 0;
}


### [AGC011D] Half Reflector

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,k,a[800010];
char s[200010];
int main(){
scanf("%d%d%s",&n,&k,s+1);
for(int i=1;i<=n;i++)a[i]=s[i]-'A';
int od=0,l=1;
for(int i=1;i<=min(k,n<<1);i++){
if((a[l]^od)==0)a[l]^=1;
else od^=1,l++,a[l+n-1]=od;
}
k-=min(k,n<<1);
if((k&1)&&(n&1))a[l]^=1;
for(int i=l;i<=l+n-1;i++)putchar((a[i]^od)+'A');
puts("");
return 0;
}


### [AGC011E] Increasing Numbers

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
struct bignum{
int a[1000010],sum;
bignum(){a[0]=1;}
void plus(int n){
int x=n;
for(int i=1;x;i++){
sum-=a[i];
a[i]+=x;
x=a[i]/10;a[i]%=10;
sum+=a[i];
if(a[0]<i)a[0]=i;
}
}
void mul(int n){
int x=0;
for(int i=1;i<=a[0]||x;i++){
a[i]=a[i]*n+x;
x=a[i]/10;a[i]%=10;
if(a[0]<i)a[i]=i;
}
}
}a;
int b;
char s[500010];
int main(){
scanf("%s",s+1);n=strlen(s+1);
for(int i=n;i>=1;i--)a.a[n-i+1]=s[i]-'0';
a.a[0]=n;
a.mul(9);
for(int i=1;i<=a.a[0];i++)a.sum+=a.a[i];
for(int k=1;k<=n;k++){
a.plus(9);b+=9;
if(a.sum<=b){
printf("%d\n",k);
break;
}
}
return 0;
}


### [AGC011F] Train Service Planning

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
int n,mod,cnt,a[200010],b[200010],sum[200010],l[200010],r[200010],lsh[400010];
int tree[800010],dp[200010];
void pushdown(int rt){
if(tree[rt]){
tree[lson]=tree[rson]=tree[rt];tree[rt]=0;
}
}
void update(int rt,int L,int R,int l,int r,int val){
if(l>r)return;
if(l<=L&&R<=r){
tree[rt]=val;return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,L,mid,l,r,val);
if(mid<r)update(rson,mid+1,R,l,r,val);
}
int query(int rt,int l,int r,int pos){
if(l==r)return tree[rt];
pushdown(rt);
int mid=(l+r)>>1;
if(pos<=mid)return query(lson,l,mid,pos);
else return query(rson,mid+1,r,pos);
}
int get(int pos){
int x=query(1,1,cnt,pos);
if(!x)return 0;
return dp[x]+(lsh[l[x]]-lsh[pos]+mod)%mod;
}
signed main(){
scanf("%lld%lld",&n,&mod);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a[i],&b[i]);
sum[i]=sum[i-1]+a[i];
if(b[i]==1&&2*a[i]>mod){
puts("-1");return 0;
}
}
for(int i=1;i<=n;i++){
if(b[i]==1){
l[i]=(mod-2ll*sum[i-1]%mod)%mod;
r[i]=(mod-2ll*sum[i]%mod)%mod;
}
else l[i]=0,r[i]=mod-1;
lsh[++cnt]=l[i];lsh[++cnt]=r[i];
}
sort(lsh+1,lsh+cnt+1);
cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
for(int i=n;i>=1;i--){
l[i]=lower_bound(lsh+1,lsh+cnt+1,l[i])-lsh;
r[i]=lower_bound(lsh+1,lsh+cnt+1,r[i])-lsh;
dp[i]=get(l[i]);
if(l[i]>r[i])update(1,1,cnt,r[i]+1,l[i]-1,i);
else update(1,1,cnt,1,l[i]-1,i),update(1,1,cnt,r[i]+1,cnt,i);
}
int ans=dp[1];
for(int i=cnt;i>=1;i--)ans=min(ans,get(i));
printf("%lld\n",ans+2*sum[n]);
return 0;
}

————————

### [AGC011A] Airport Bus

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,c,k,ans,a[100010];
int main(){
scanf("%d%d%d",&n,&c,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
int cnt=0,t=0;
for(int i=1;i<=n;i++){
if(cnt>=c||a[i]>t)t=a[i]+k,cnt=1,ans++;
else cnt++;
}
printf("%d\n",ans);
return 0;
}


### [AGC011B] Colorful Creatures

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n,ans,a[100010];
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(a[i+1]<=2*a[i])ans++;
else ans=0;
a[i+1]+=a[i];
}
printf("%lld\n",ans);
return 0;
}


### [AGC011C] Squared Graph

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a,b,c,col[100010];
struct node{
int v,next;
}edge[400010];
void add(int u,int v){
}
bool dfs(int x,int c){
col[x]=c;
bool jud=true;
if(col[edge[i].v]){
if(col[edge[i].v]==col[x])jud=false;
}
else jud&=dfs(edge[i].v,3-c);
}
return jud;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
}
for(int i=1;i<=n;i++){
if(col[i])continue;
else{
if(dfs(i,1))b++;
else a++;
}
}
long long ans=0;
int cnt=0;
for(int i=1;i<=a;i++)ans+=2*cnt+1,cnt++;
for(int i=1;i<=b;i++)ans+=2*cnt+2,cnt+=2;
cnt=n-c;
for(int i=1;i<=c;i++)ans+=2*cnt+1,cnt++;
printf("%lld\n",ans);
return 0;
}


### [AGC011D] Half Reflector

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,k,a[800010];
char s[200010];
int main(){
scanf("%d%d%s",&n,&k,s+1);
for(int i=1;i<=n;i++)a[i]=s[i]-'A';
int od=0,l=1;
for(int i=1;i<=min(k,n<<1);i++){
if((a[l]^od)==0)a[l]^=1;
else od^=1,l++,a[l+n-1]=od;
}
k-=min(k,n<<1);
if((k&1)&&(n&1))a[l]^=1;
for(int i=l;i<=l+n-1;i++)putchar((a[i]^od)+'A');
puts("");
return 0;
}


### [AGC011E] Increasing Numbers

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
struct bignum{
int a[1000010],sum;
bignum(){a[0]=1;}
void plus(int n){
int x=n;
for(int i=1;x;i++){
sum-=a[i];
a[i]+=x;
x=a[i]/10;a[i]%=10;
sum+=a[i];
if(a[0]<i)a[0]=i;
}
}
void mul(int n){
int x=0;
for(int i=1;i<=a[0]||x;i++){
a[i]=a[i]*n+x;
x=a[i]/10;a[i]%=10;
if(a[0]<i)a[i]=i;
}
}
}a;
int b;
char s[500010];
int main(){
scanf("%s",s+1);n=strlen(s+1);
for(int i=n;i>=1;i--)a.a[n-i+1]=s[i]-'0';
a.a[0]=n;
a.mul(9);
for(int i=1;i<=a.a[0];i++)a.sum+=a.a[i];
for(int k=1;k<=n;k++){
a.plus(9);b+=9;
if(a.sum<=b){
printf("%d\n",k);
break;
}
}
return 0;
}


### [AGC011F] Train Service Planning

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
int n,mod,cnt,a[200010],b[200010],sum[200010],l[200010],r[200010],lsh[400010];
int tree[800010],dp[200010];
void pushdown(int rt){
if(tree[rt]){
tree[lson]=tree[rson]=tree[rt];tree[rt]=0;
}
}
void update(int rt,int L,int R,int l,int r,int val){
if(l>r)return;
if(l<=L&&R<=r){
tree[rt]=val;return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,L,mid,l,r,val);
if(mid<r)update(rson,mid+1,R,l,r,val);
}
int query(int rt,int l,int r,int pos){
if(l==r)return tree[rt];
pushdown(rt);
int mid=(l+r)>>1;
if(pos<=mid)return query(lson,l,mid,pos);
else return query(rson,mid+1,r,pos);
}
int get(int pos){
int x=query(1,1,cnt,pos);
if(!x)return 0;
return dp[x]+(lsh[l[x]]-lsh[pos]+mod)%mod;
}
signed main(){
scanf("%lld%lld",&n,&mod);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a[i],&b[i]);
sum[i]=sum[i-1]+a[i];
if(b[i]==1&&2*a[i]>mod){
puts("-1");return 0;
}
}
for(int i=1;i<=n;i++){
if(b[i]==1){
l[i]=(mod-2ll*sum[i-1]%mod)%mod;
r[i]=(mod-2ll*sum[i]%mod)%mod;
}
else l[i]=0,r[i]=mod-1;
lsh[++cnt]=l[i];lsh[++cnt]=r[i];
}
sort(lsh+1,lsh+cnt+1);
cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
for(int i=n;i>=1;i--){
l[i]=lower_bound(lsh+1,lsh+cnt+1,l[i])-lsh;
r[i]=lower_bound(lsh+1,lsh+cnt+1,r[i])-lsh;
dp[i]=get(l[i]);
if(l[i]>r[i])update(1,1,cnt,r[i]+1,l[i]-1,i);
else update(1,1,cnt,1,l[i]-1,i),update(1,1,cnt,r[i]+1,cnt,i);
}
int ans=dp[1];
for(int i=cnt;i>=1;i--)ans=min(ans,get(i));
printf("%lld\n",ans+2*sum[n]);
return 0;
}