A. Favorite Sequence
观察发现前一半大概是2i-1分布,后一半是n-2i分布.然后代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int a[N],b[N];
int main()
{
int T;
cin>>T;
while(T--)
{
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=(n+1)/2;i++)
{
b[i*2-1]=a[i];
}int id=1;
for(int i=n;i>(n+1)/2;i--)
{
b[id<<1]=a[i];
id++;
}
for(int i=1;i<=n;i++) cout<<b[i]<<' ';
puts("");
}
return 0;
}B. Last Year's Substring
可以想到只能删一次,答案要么保留在前面,后面,或者前后连接.直接判断一下就可以了.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int a[N],b[N];
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
string s;
cin>>s;
if(s[0]=='2'&&s[1]=='0'&&s[2]=='2'&&s[3]=='0') puts("YES");
else if(s[n-4]=='2'&&s[n-3]=='0'&&s[n-2]=='2'&&s[n-1]=='0') puts("YES");
else if(s[0]=='2'&&s[n-3]=='0'&&s[n-2]=='2'&&s[n-1]=='0') puts("YES");
else if(s[0]=='2'&&s[1]=='0'&&s[n-2]=='2'&&s[n-1]=='0') puts("YES");
else if(s[0]=='2'&&s[1]=='0'&&s[2]=='2'&&s[n-1]=='0') puts("YES");
else puts("NO");
}
return 0;
}C. Unique Number
数据范围很小,直接打表即可得到答案.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
ll a[51]={1,2,3,4,5,6,7,8,9,19,29,39,49,59,69,79,89,189,289,389,489,589,689,789,1789,2789,3789,4789,5789,6789,16789,26789,36789,46789,56789,156789,256789,356789,456789,1456789,2456789,3456789,13456789,23456789,123456789};
int main()
{
int T;cin>>T;
while(T--)
{
int x;
cin>>x;
if(x<46) cout<<a[x-1]<<endl;
else puts("-1");
}
return 0;
}附赠打表代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int a[N],b[N];
int sum(int x)
{
int res=0;
while(x>0)
{
res+=(x%10);
x/=10;
}return res;
}
bool ck(int x)
{
bool vis[10];memset(vis,false,sizeof vis);
while(x>0)
{
if(!vis[x%10]) vis[x%10]=true,x/=10;
else return false;
}return true;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;int flag=0;
for(int i=1;i<=2e7;i++)
{
if(ck(i)&&(sum(i)==n))
{
printf("%d\n",i);
flag=1;
break;
}
}if(!flag) puts("-1");
}
return 0;
}D. Add to Neighbour and Remove
枚举可能的前缀作为答案,然后检测答案是不是可行,最后输出即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e3+50;
ll a[N],sum[N];
int main()
{
int T;cin>>T;
while(T--)
{
int n;
scanf("%d",&n);
// for(int i=1;i<=n;i++) sum[i]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}int ans=n-1;
for(int i=1;i<=n;i++)
{
bool flag=true;int cnt=i-1;
for(int j=i+1;j<=n;)
{
int res=0;
while(res<sum[i]&&j<=n) res+=a[j],cnt++,j++;
cnt--;
// if(i==2) cout<<res<<endl;
if(res!=sum[i]) {flag=false;break;}
}//cout<<flag<<endl;
if(flag) ans=min(ans,cnt);
}printf("%d\n",ans);
}
return 0;
}E1. Close Tuples (easy version)
树状数组直接模拟这个取值就好了.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int n;
int a[N];
int sum[2][N];
int lowbit(int x)
{
return x&(-x);
}
void add(int pos,int val,int op)
{
while(pos<=n)
{
sum[op][pos]+=val;
pos+=lowbit(pos);
}
}
ll query(int pos,int op)
{
ll res=0;
while(pos)
{
res+=sum[op][pos];
pos-=lowbit(pos);
}return res;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
add(a[i],1,1);
}ll ans=0;
for(int i=1;i<=n;i++)
{
add(a[i],-1,1);
ans+=(query(min(a[i]+2,n),0)-query(min(a[i]+1,n),0))*(query(min(a[i]+2,n),1)-query(max(a[i]-1,0),1));//2 2 0
ans+=(query(min(a[i]+1,n),0)-query(min(a[i]+0,n),0))*(query(min(a[i]+2,n),1)-query(max(a[i]-2,0),1));//1 1 -1
ans+=(query(min(a[i],n),0)-query(max(a[i]-1,0),0))*(query(min(a[i]+2,n),1)-query(max(a[i]-3,0),1));//0 2 -2
ans+=(query(max(a[i]-1,0),0)-query(max(a[i]-2,0),0))*(query(min(a[i]+1,n),1)-query(max(a[i]-3,0),1));//-1 1 -2
ans+=(query(max(a[i]-2,0),0)-query(max(a[i]-3,0),0))*(query(min(a[i],n),1)-query(max(a[i]-3,0),1));//-2
add(a[i],1,0);
}printf("%lld\n",ans);
for(int i=1;i<=n;i++) add(a[i],-1,0);
}
return 0;
}
E2. Close Tuples (hard version)
k只有100,同上暴力即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
const int mod=1e9+7;
int n;
int a[N];
int sum[N];
int lowbit(int x)
{
return x&(-x);
}
void add(int pos,int val)
{
while(pos<=n)
{
sum[pos]+=val;
pos+=lowbit(pos);
}
}
ll query(int pos)
{
ll res=0;
while(pos)
{
res+=sum[pos];
pos-=lowbit(pos);
}return res;
}
ll fact[N],ivf[N];
ll qp(ll A,ll B)
{
ll res=1;
while(B)
{
if(B&1) res=res*A%mod;
A=A*A%mod;
B>>=1;
}
return res;
}
inline ll C(ll A,ll B)
{
if(B>A) return 0;
return fact[A]%mod*ivf[B]%mod*ivf[A-B]%mod;
}
void init()
{
fact[1]=1;fact[0]=1;
for(int i=2;i<=N-5;i++)
{
fact[i]=i*fact[i-1]%mod;
}ivf[N-5]=qp(fact[N-5],mod-2);
for(int i=N-5;i>=1;i--)
{
ivf[i-1]=ivf[i]*i%mod;
}
}
int main()
{
int T,m,k;
scanf("%d",&T);
init();
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
add(a[i],1);
}ll ans=0;
for(int i=1;i<=n;i++)
{
int num=query(i)-query(i-1);
if(num>=m) ans+=C(num,m);ans%=mod;
ll cnt=query(min(i+k,n))-query(i);
for(int j=1;j<=min(m-1,num);j++)
{
ans+=C(num,j)*C(cnt,m-j);
ans%=mod;
}
}printf("%lld\n",ans);
for(int i=1;i<=n;i++) add(a[i],-1);
}
return 0;
}F. The Treasure of The Segments
优先队列维护树状数组更新即可.
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int ls[N];
struct Tree{
int l,r;
}w[N];
bool cmp(Tree a,Tree b)
{
if(a.l==b.l) return a.r<b.r;
else return a.l<b.l;
}
int sum[N],n;
int lowbit(int x) {return x&(-x);}
void add(int pos,int val)
{
while(pos<=2*n)
{
sum[pos]+=val;
pos+=lowbit(pos);
}
}
int query(int pos)
{
int res=0;
while(pos)
{
res+=sum[pos];
pos-=lowbit(pos);
}return res;
}
struct Q{
int l,r;
friend bool operator<(const Q &A,const Q &B)
{
if(A.r==B.r) return A.l<B.l;
else return A.r>B.r;
}
};
priority_queue<Q>q;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int id=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i].l,&w[i].r);
ls[++id]=w[i].l,ls[++id]=w[i].r;
}sort(ls+1,ls+1+id);
int cnt=unique(ls+1,ls+1+id)-ls-1;
for(int i=1;i<=n;i++)
{
w[i].l=lower_bound(ls+1,ls+1+cnt,w[i].l)-ls;
w[i].r=lower_bound(ls+1,ls+1+cnt,w[i].r)-ls;
}//离散化区间.
int ans=0;
sort(w+1,w+1+n,cmp);
int l=1,r=1;
//for(int i=1;i<=n;i++) cout<<w[i].l<<' '<<w[i].r<<endl;
for(int i=1;i<=n;i++)//扫描n个区间.
{
while(q.size()&&q.top().r<w[i].l&&l<r) {add(q.top().l,-1),l++;q.pop();}
while(w[i].r>=w[r].l&&r<=n) {add(w[r].l,1);q.push({w[r].l,w[r].r}),r++;}
ans=max(query(w[i].r),ans);
//cout<<ans<<endl;
}//while(l<r) add(w[l].l,-1),l++;
printf("%d\n",n-ans);
/*while(q.size())
{
cout<<q.top().l<<' '<<q.top().r<<endl;
q.pop();
}*/
while(q.size()) { add(q.top().l,-1),q.pop();}
}
return 0;
}
/*
1
6
1 6
3 6
4 4
4 6
5 7
7 7
*/
京公网安备 11010502036488号