Lvat_s Blog

bzoj上的坑题……

数组要放大，必须开long long

#include<cstdio>
#include<algorithm>
using namespace std;

struct Go{
long long add,dec,rev;
long long i;
friend bool operator<(Go a,Go b){
	if(a.rev>=0 && b.rev>=0){return a.dec<b.dec;}
	if(a.rev<0 && b.rev<0){return a.add>b.add;}
	if(a.rev>=0 && b.rev<0)return 1;
	if(a.rev<0 && b.rev>=0)return 0;
}
}da[1000005];

long long n,z;

int main(){
freopen("3709.in","r",stdin);
freopen("3709.out","w",stdout);
scanf("%lld %lld",&n,&z);
for(long long i=1;i<=n;i++)scanf("%lld %lld",&da[i].dec,&da[i].add),da[i].rev=da[i].add-da[i].dec,da[i].i=i;
sort(da+1,da+1+n);
for(long long i=1;i<=n;i++){
	z-=da[i].dec;
	if(z<=0){puts("NIE");return 0;}
	z+=da[i].add;
}
puts("TAK");
for(long long i=1;i<=n;i++)printf("%lld ",da[i].i);
return 0;
}

暴力。。

#include<cstdio>

int n,cir[25],sum[25],ans=0;

int main(){
freopen("1800.in","r",stdin);
freopen("1800.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&cir[i]);sum[i]=cir[i]+sum[i-1];}
for(int i=1;i<=n;i++){
	for(int j=i+1;j<=n;j++){
		for(int k=j+1;k<=n;k++){
			for(int l=k+1;l<=n;l++){
				if(sum[j-1]-sum[i-1]==sum[l-1]-sum[k-1] && sum[k-1]-sum[j-1]==sum[n]-sum[l-1]+sum[i-1])ans++;
			}
		}
	}
}
printf("%d\n",ans);
return 0;
}

第一次写分块，挑了这题写……

然后调了一个晚上。

各种猎奇的错误都被我犯了……

人傻就是要多做题。

分块+二分

参考hzwer的

弱智错误记录:

1.数组要注意清空:这个在WC2016上已经让我的T1 60->0了……以后要认真吸取教训

2.不要乱开局部数组:这样会显著增大常数

3.要知道自己二分的是什么，不要搞着搞着就搞乱了

以上

Claris也在坚持刷题……太可怕了，本身实力超强还在刷……orzzzz

#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

int n,c,m,a[100005],f[1505][1505],fir[100005],las[100005],block,ans=0,L[1505],R[1505],belong[100005],tmp[100005],cnt;

struct Data{
int a,b;
friend bool operator<(Data a,Data b){
return (a.a<b.a)||(a.a==b.a && a.b<b.b);
}
}data[100005];

pair<int,int> GetLR(int L,int R){
L=(L+ans)%n+1;
R=(R+ans)%n+1;
if(L>R)swap(L,R);
return make_pair(L,R);
}

void Pre(){
for(int i=1;i<=cnt;i++){
	for(int j=L[i];j<=n;j++)tmp[a[j]]=0;
	int tot=0;
	for(int j=L[i];j<=n;j++){
		if(tmp[a[j]]%2==0 && tmp[a[j]])tot--;
		tmp[a[j]]++;
		if(tmp[a[j]]%2==0)tot++;
		f[i][belong[j]]=tot;
	}
}
//for(int i=belong[1];i<=belong[n];i++){for(int j=i;j<=belong[n];j++){printf("%d ",f[i][j]);}putchar('\n');}
for(int i=1;i<=n;i++)data[i].a=a[i],data[i].b=i;
sort(data+1,data+n+1);
for(int i=1;i<=n;i++){
	if(fir[data[i].a]==0)fir[data[i].a]=i;
	las[data[i].a]=i ;
}
}

int Ef_Fir(int x,int v){
int tp=214748364,l=fir[v],r=las[v];
while(l<=r){
	int mid=l+r>>1;
	if(x>data[mid].b)l=mid+1;
	else {r=mid-1;tp=mid;}
}
return tp;
}

int Ef_Las(int x,int v){
int tp=0,l=fir[v],r=las[v];
while(l<=r){
	int mid=l+r>>1;
	if(x<data[mid].b)r=mid-1;
	else {l=mid+1;tp=mid;}
}
return tp;
}

int Ef(int x,int y,int v){
//printf("%d %d %d | EF:%d %d\n",x,y,v,Ef_Las(y,v),Ef_Fir(x,v));
return max(Ef_Las(y,v)-Ef_Fir(x,v)+1,0);
}

int solve(int l,int r){
//printf("LR:%d %d\n",l,r);
int nwans=0,kl=belong[l],kr=belong[r];
if(kl+1==kr || kl==kr){
	for(int i=l;i<=r;i++){
		if(tmp[a[i]])continue;
		int sp=Ef(l,r,a[i]);
		if(sp%2==0){nwans++;}
		//printf("%d %d %d\n",l,r,a[i]);
		tmp[a[i]]=1;
	}
	for(int i=l;i<=r;i++)tmp[a[i]]=0;
	return nwans;
}
else {
    int fs=L[kl+1],la=R[kr-1];
    nwans=f[kl+1][kr-1];
    //printf("%d %d | NW_ANS1:%d\n",kl,kr,nwans);
    for(int i=l;i<fs;i++){
		if(tmp[a[i]])continue;
		int sp=Ef(l,r,a[i]),sp2=Ef(fs,la,a[i]);
		if(sp2%2==0 && sp%2 && sp2!=0){nwans--;}
		if((sp2%2 || sp2==0) && sp%2==0){nwans++;}
		//printf("SP:%d SP2:%d_%d_",sp,sp2,nwans);
		tmp[a[i]]=1;
    }
    //printf("NW_ANS2:%d\n",nwans);
    for(int i=la+1;i<=r;i++){
		if(tmp[a[i]])continue;
		int sp=Ef(l,r,a[i]),sp2=Ef(fs,la,a[i]);
		if(sp2%2==0 && sp%2 && sp2!=0){nwans--;}
		if((sp2%2 || sp2==0) && sp%2==0){nwans++;}
		//printf("SP:%d SP2:%d_%d_",sp,sp2,nwans);
		tmp[a[i]]=1;
    }
    for(int i=l;i<fs;i++)tmp[a[i]]=0;
    for(int i=la+1;i<=r;i++)tmp[a[i]]=0;
    return nwans;
}
}

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("2821.in","r",stdin);
freopen("2821.out","w",stdout);
Read(n);Read(c);Read(m);
for(int i=1;i<=n;i++){
	Read(a[i]);
}
block=(int)sqrt((double)n/log(n)*log(2));
cnt=n/block+(n%block!=0);
for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;
for(int i=1;i<=cnt;i++)L[i]=R[i-1]+1,R[i]=i*block;
R[cnt]=n;
Pre();
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=m;i++){
	int tl,tr;
	Read(tl);Read(tr);
    pair<int,int> Ask=GetLR(tl,tr);
    //pair<int,int> Ask=make_pair(tl,tr);
    ans=solve(Ask.first,Ask.second);
    printf("%d\n",ans);
}
return 0;
}

真的是完美的滚粗，不能更滚粗了……第一次去WC滚粗很正常gqy等一群大爷也第一次去就Ag了……

day 0

到了绵阳……和cjy wlp lyz三个大爷住在一起 感觉十分资瓷

晚上睡觉感觉很冷谁叫你不把衣服放被子上

day 1

早上Picks的课上完后，觉的自己幼儿园毕业都算不上

下午睡掉了

晚上隔膜

营员交流wzf和nxy讲的东西完全不会啊

day 2

早上难得听了课！但是还是睡掉了

下午继续睡觉

晚上隔膜

营员交流lzz还是很资瓷的

day3

早上不知所云

下午评测系统十分资瓷！

晚上隔膜

晚上试机似乎ak了……为接下来的爆0滚粗埋下伏笔

day4

早上做题啦！

三题都好难啊

T1写了一个多合一程序

T2写了个连样例都没过的暴力

T3直接弃疗

得分0+5+0

原来T1数组少清空1个……吐血

wyx强行110 Au

lzz wzf都进队了(rank2 rank3)都是160

nxy好像写挂了一题……默哀

wlp90

cjy100

晚上的晚会还是很欢乐的

本校几位大爷都表演去了

后来直接隔膜来抚慰我受伤的心情

day5

去了纪念馆

心情更加沉重了

day6

早上坐飞机回芜湖了……

滚粗胸牌回家

希望省选不能再这样滚粗了……