期望：100 + 40 + 50 = 190
实际：60 + 10 + 50 = 120
考得好炸啊！！T1数组开小了炸掉40，T2用 int 读入 long long ,int存储 long long 炸掉 20
T3可以吧for维护最大值变成o(1)，但是木想到啊，只想写暴力了。。。w(ﾟДﾟ)w
最近考试低级错误一个接一个啊！！noip肿么玩啊。。简直没法好好玩耍了。
感觉要凉~~~~(>_<)~~~~
wfj竟然敢奶我：看我奶死她：：
wfj AK NOIP wfj AK 省选（省队姐） wfj AK NOI wfj AK IOI
原来以为我的数组没开小，是AC了的，因为特别注意了数组，但是。。。没想到树状数组的数组开小了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long ans;
int n,k,tot,numt;
int num[],F[];
int val[],f[],g[];
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 fastpow(long long a,long long b){
long long s=;
for(;b;b>>=){
if(b&) s=s*a%k;
a=a*a%k;
}
return s;
}
int lowbit(int x){
return x&(-x);
}
void change(int x){
for(int i=x;i<=numt;i+=lowbit(i))
F[i]+=;
}
int query(int x){
int bns=;
for(int i=x;i;i-=lowbit(i))
bns+=F[i];
return bns;
}
int ff(int now){
return fastpow(now,val[now]);
}
int gg(int now){
return fastpow(val[now],now);
}
int main(){
//freopen("lpp.in","r",stdin);
freopen("calc.in","r",stdin);
freopen("calc.out","w",stdout);
n=read();k=read();
for(int i=;i<=n;i++){
val[i]=read();
f[i]=ff(i);g[i]=gg(i);
num[++tot]=f[i];
num[++tot]=g[i];
}
sort(num+,num++tot);
numt=unique(num+,num++tot)-num-;
for(int i=;i<=n;i++){
f[i]=lower_bound(num+,num++numt,f[i])-num;
g[i]=lower_bound(num+,num++numt,g[i])-num;
}
for(int i=;i<=n;i++){
ans+=query(numt)-query(g[i]);
change(f[i]);
}
cout<<ans;
}
60分数组开小了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long ans;
int n,k,tot,numt;
int num[],F[];
int val[],f[],g[];
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 fastpow(long long a,long long b){
long long s=;
for(;b;b>>=){
if(b&) s=s*a%k;
a=a*a%k;
}
return s;
}
int lowbit(int x){
return x&(-x);
}
void change(int x){
for(int i=x;i<=numt;i+=lowbit(i))
F[i]+=;
}
int query(int x){
int bns=;
for(int i=x;i;i-=lowbit(i))
bns+=F[i];
return bns;
}
int ff(int now){
return fastpow(now,val[now]);
}
int gg(int now){
return fastpow(val[now],now);
}
int main(){
//freopen("lpp.in","r",stdin);
freopen("calc.in","r",stdin);
freopen("calc.out","w",stdout);
n=read();k=read();
for(int i=;i<=n;i++){
val[i]=read();
f[i]=ff(i);g[i]=gg(i);
num[++tot]=f[i];
num[++tot]=g[i];
}
sort(num+,num++tot);
numt=unique(num+,num++tot)-num-;
for(int i=;i<=n;i++){
f[i]=lower_bound(num+,num++numt,f[i])-num;
g[i]=lower_bound(num+,num++numt,g[i])-num;
}
for(int i=;i<=n;i++){
ans+=query(numt)-query(g[i]);
change(f[i]);
}
cout<<ans;
}
100
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[];
int n,r,enan;
long long k;
int fv[];
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;
}
long long readll(){
long long 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 work(){
int bns=0x7f7f7f7f;
for(int i=;i<=n;i++)
bns=min(bns,fv[i]);
return bns;
}
void change(int x){
for(int i=max(,x-r);i<=min(n,x+r);i++)
fv[i]+=;
}
void nochange(int x){
for(int i=max(,x-r);i<=min(n,x+r);i++)
fv[i]-=;
}
void dfs(int now){
if(now==k+){
enan=min(enan,work());
return ;
}
int minn=0x7f7f7f7f;
for(int i=;i<=n;i++)
if(fv[i]<minn) minn=fv[i];
for(int i=;i<=n;i++)
if(fv[i]==minn)
for(int j=max(,i-r);j<=min(n,i+r);j++){
change(j);
dfs(now+);
nochange(j);
}
}
int main(){
freopen("Game.in","r",stdin);
freopen("Game.out","w",stdout);
n=read();r=read();k=readll();
for(int i=;i<=n;i++) a[i]=read();
if(r==){
sort(a+,a++n);
long long sum=;
for(int i=;i<=n;i++)
sum+=a[n]-a[i];
if(k>=sum){
k-=sum;k/=n;
long long ans=1ll*k+1ll*a[n];
printf("%I64d",ans);
return ;
}
else{
for(int i=n;i>=;i--){
sum=;
for(int j=;j<=i;j++)
sum+=a[i]-a[j];
if(sum>k) continue;
else if(sum==k){
printf("%d",a[i]);
return ;
}
else{
k-=sum;k/=i;
long long ans=1ll*a[i]+1ll*k;
printf("%I64d",ans);
return ;
}
}
}
}
else if(n<=){
enan=0x7f7f7f7f;
for(int i=;i<=n;i++)
for(int j=max(,i-r);j<=min(n,i+r);j++)
fv[j]+=a[i];
dfs();
printf("%d",enan);
return ;
}
else{
sort(a+,a++n);
long long sum=;
for(int i=;i<=n;i++)
sum+=a[n]-a[i];
if(k>=sum){
k-=sum;k/=n;
printf("%d",k+a[n]);
return ;
}
}
}
/*
5 0 6
5 4 3 4 9
*/
40分暴力
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
long long n,R,k;
long long l,r,mid,ans;
long long a[],b[],cf[],sum[];
long long read(){
long long x=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
long long query(long long ll,long long rr){
rr=min(rr,n);
if(ll<) return sum[rr];
else return sum[rr]-sum[ll];
}
bool judge(){
memset(cf,,sizeof(cf));
long long sumcf=,res=k;
for(long long i=;i<=n;i++) a[i]=b[i];
for(long long i=;i<=n;i++){
sumcf+=cf[i];
a[i]+=sumcf;
if(a[i]<mid){
sumcf+=mid-a[i];
cf[i+*R+]-=mid-a[i];
res-=mid-a[i];
}
if(res<) return false;
}
return true;
}
int main(){
n=read();R=read();k=read();
for(int i=;i<=n;i++){
a[i]=read();
sum[i]=sum[i-]+a[i];
}
for(int i=;i<=n;i++) a[i]=query(i-R-,i+R);
for(int i=;i<=n;i++) b[i]=a[i];
l=;r=3e18;
while(l<=r){
mid=(l+r)/;
if(judge()){
l=mid+;
ans=mid;
}
else r=mid-;
}
cout<<ans;
}
100
唉~就差那么两行。果然思想要上去，还是要有AC的志向的，不能只写暴力。QwQ
/*
期望：50
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k;
int fa[],val[];
struct nond{ int u,v,w; }edge[];
struct none{ int id,xmax,ans; }ques[];
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 cmp(nond a,nond b){ return a.w<b.w; }
int cmp2(none a,none b){ return a.id<b.id; }
int cmp1(none a,none b){ return a.xmax<b.xmax; }
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main(){
//freopen("lpp.in","r",stdin);
freopen("Graph.in","r",stdin);
freopen("Graph.out","w",stdout);
n=read();m=read();k=read();
for(int i=;i<=m;i++){
edge[i].u=read();
edge[i].v=read();
edge[i].w=read();
}
sort(edge+,edge++m,cmp);
for(int i=;i<=k;i++){
ques[i].xmax=read();
ques[i].id=i;
}
sort(ques+,ques++k,cmp1);
int quepos=;
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++){
if(quepos>k) break;
int dx=find(edge[i].u);
int dy=find(edge[i].v);
if(edge[i].w>ques[quepos].xmax){
int maxn=-0x7f7f7f7f;
for(int j=;j<=n;j++)
if(find(j)==j)
maxn=max(maxn,val[fa[j]]);
while(quepos<=k&&edge[i].w>ques[quepos].xmax){
ques[quepos].ans=maxn;
quepos++;
}
}
if(dx==dy){
val[dx]+=edge[i].w;
continue;
}
fa[dy]=dx;
val[dx]+=val[dy]+edge[i].w;
val[dy]=;
}
int maxn=-0x7f7f7f7f;
for(int i=;i<=n;i++)
if(find(i)==i)
maxn=max(maxn,val[fa[i]]);
while(quepos<=k){
ques[quepos].ans=maxn;
quepos++;
}
sort(ques+,ques++k,cmp2);
for(int i=;i<=k;i++)
printf("%d\n",ques[i].ans);
}
50分暴力
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k,ans=;
int fa[],val[];
struct nond{ int u,v,w; }edge[];
struct none{ int id,xmax,ans; }ques[];
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 cmp(nond a,nond b){ return a.w<b.w; }
int cmp2(none a,none b){ return a.id<b.id; }
int cmp1(none a,none b){ return a.xmax<b.xmax; }
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main(){
//freopen("lpp.in","r",stdin);
//freopen("Graph.in","r",stdin);
//freopen("Graph.out","w",stdout);
n=read();m=read();k=read();
for(int i=;i<=m;i++){
edge[i].u=read();
edge[i].v=read();
edge[i].w=read();
}
sort(edge+,edge++m,cmp);
for(int i=;i<=k;i++){
ques[i].xmax=read();
ques[i].id=i;
}
sort(ques+,ques++k,cmp1);
int quepos=;
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++){
if(quepos>k) break;
int dx=find(edge[i].u);
int dy=find(edge[i].v);
if(edge[i].w>ques[quepos].xmax)
while(quepos<=k&&edge[i].w>ques[quepos].xmax){
ques[quepos].ans=ans;
quepos++;
}
if(dx==dy){
val[dx]+=edge[i].w;
if(val[dx]>ans) ans=val[dx];
continue;
}
fa[dy]=dx;
val[dx]+=val[dy]+edge[i].w;
val[dy]=;
if(val[dx]>ans) ans=val[dx];
}
while(quepos<=k){
ques[quepos].ans=ans;
quepos++;
}
sort(ques+,ques++k,cmp2);
for(int i=;i<=k;i++)
printf("%d\n",ques[i].ans);
}
100