4
23
2016
0

BestCoder Round #81

Machine
有一个机器,它有 m(2m30) 个彩灯和一个按钮。每按下按钮时,最右边的彩灯会发生一次变换。变换为:
1. 如果当前状态为红色,它将变成绿色;
2.如果当前状态为绿色,它将变成蓝色;
3.如果当前状态为蓝色,它将变成红色,并且它左边的彩灯(如果存在)也会发生一次变换。
初始状态下所有的灯都是红色的。
询问按下按钮
n(1n<2​63​​) 次以后各个彩灯的颜色。
 
想到了是三进制数,没开LL,中间值没LL WA了2次,软弱无力
n的三进制表示的最低的m位,即求 n mod 3^m​​的三进制表示
注意%3^m结果才是3^0~3^(m-1)
复杂度O(logn)O(m)
typedef long long LL;
const int N=35;
int tt,n,a[N];
LL m,p;
int main()
{
//    freopen("A.txt","r",stdin);
    scanf("%d",&tt);
    while(tt--){
    	scanf("%d%lld",&n,&m);
    	p=m;memset(a,0,sizeof(a));
    	F(i,1,n){
     		LL cur=(LL)a[i]+p;
   	  		a[i]=(LL)cur%3;
   	   		p=(LL)cur/3;
    	}
    	D(i,n,1){
        	if(a[i]==0) printf("R");
        	else if(a[i]==1) printf("G");
        	else if(a[i]==2) printf("B");
    	}
    	printf("\n");
    }
    return 0;
}

 


Matrix
有一个nm列的矩阵(1n1000,1m1000),在这个矩阵上进行q(1q100,000) 个操作:
1 x y: 交换矩阵MM的第x行和第y(1x,yn);
2 x y: 交换矩阵
MM的第x列和第y(1x,ym);
3 x y: 对矩阵
MM的第x行的每一个数加上y(1xn,1y10,000);
4 x y: 对矩阵
MM的第x列的每一个数加上y(1xm,1y10,000);
 
把问题想复杂了,1q100,000显然每个操作都需要O(1)完成,显然对整行整列打标记即可
可当时考虑了类似线段树的标记顺序问题,还想用vector来存放对每个数操作位置,太偏了
Key:
因为交换总是以整个行或者整个列为单位进行的,
所以无论怎么移动,在一行的数字,最终还是会在一行,在一列的数字,最终还是会在一列,无论怎么交换。 
用数组模拟指针指向:
对于交换行、交换列的操作,分别记录当前状态下每一行、每一列是原始数组的哪一行、哪一列即可。对每一行、每一列加一个数的操作,也可以两个数组分别记录。
注意当交换行、列的同时,也要交换增量数组。
输出时通过索引找到原矩阵中的值,再加上行、列的增量。
复杂度O(q+mn)
具体一看代码就明白
//HDU 1A
const int N=1000+5;
int n,m,q;
int g[N][N],a[N],b[N],ac[N],bc[N];
int main()
{
//	freopen("B.txt","r",stdin);
	int tt;scanf("%d",&tt);
	while(tt--){
		mec(g,0);mec(a,0);mec(b,0);
		mec(ac,0);mec(bc,0);
		scanf("%d%d%d",&n,&m,&q);
		F(i,1,n) F(j,1,m) scanf("%d",&g[i][j]);
		F(i,1,n) a[i]=i;
		F(i,1,m) b[i]=i;
		while(q--){
			int opt,x,y;
			scanf("%d%d%d",&opt,&x,&y);
			switch(opt){
				case 1:
					swap(a[x],a[y]);
					swap(ac[x],ac[y]);
					break;
				case 2:
					swap(b[x],b[y]);
					swap(bc[x],bc[y]);
					break;
				case 3:ac[x]+=y;break;
				case 4:bc[x]+=y;break;
			}
		}
		F(i,1,n){
			F(j,1,m){
			printf("%d",g[a[i]][b[j]]+ac[i]+bc[j]);
			if(j!=m) printf(" ");
		}
		printf("\n");
		}
	}
	return 0;
}

String

有一个 10长度1,000,000 的字符串,仅由小写字母构成。求有多少个子串,包含有至少k(1k26)个不同的字母?
 
比赛时看到子串稍稍有点方,还以为要用字符串的高级算法..然后就跪了
固定左端点,移动右端点,[l,r]的不同字母个数是单调不降的!
所以固定左端点,满足条件的右端点的位置是单增的
——l相同时r每次从上一次的位置出发即可。
双指针法的思想很常用!
 
有一个明显的性质:
如果子串(i,j)包含了至少k个不同的字符,那么子串(i,k),(j<k<length)也包含了至少k个不同字符。
因此对于每一个左边界,只要找到最小的满足条件的右边界,就能在O(1)时间内统计完所有以这个左边界开始的符合条件的子串。
寻找这个右边界,是经典的追赶法(尺取法,双指针法)问题
维护两个指针(数组下标),轮流更新左右边界,同时累加答案即可。复杂度O(length(S))
//T了2发,加读入优化才过的 
typedef long long LL;
char s[1000000+5];int K,len,l,r;
LL ans;bool flag;
int num[30];
inline int getint()
{
	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 calc()
{
	int res=0;
	F(i,0,25) if(num[i]>0) res++;
	return res;
}
int main()
{
//	freopen("C.txt","r",stdin); 
	int tt=getint();
	while(tt--){
		mec(num,0);ans=0;flag=false;
		scanf("%s",s);K=getint();
		r=-1;
		len=strlen(s);
		F(l,0,len-1){
//			r=l;
			while(calc()<K){
				r++;
				if(r==len){flag=true;break;}
				num[s[r]-'a']++;
			}
			if(flag) break;
			ans+=(LL)(len-r);
			num[s[l]-'a']--;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

 

 

Category: bestcoder | Tags: 乱搞 组合数学 | Read Count: 233

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com