Machine
有一个机器，它有 m(2≤m≤30) 个彩灯和一个按钮。每按下按钮时，最右边的彩灯会发生一次变换。变换为：
1. 如果当前状态为红色，它将变成绿色；
2.如果当前状态为绿色，它将变成蓝色；
3.如果当前状态为蓝色，它将变成红色，并且它左边的彩灯（如果存在）也会发生一次变换。
初始状态下所有的灯都是红色的。
询问按下按钮 n(1≤n<263) 次以后各个彩灯的颜色。
询问按下按钮 n(1≤n<263) 次以后各个彩灯的颜色。
想到了是三进制数,没开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
有一个n行m列的矩阵(1≤n≤1000,1≤m≤1000)，在这个矩阵上进行q(1≤q≤100,000) 个操作：
1 x y: 交换矩阵MM的第x行和第y行(1≤x,y≤n);
2 x y: 交换矩阵MM的第x列和第y列(1≤x,y≤m);
3 x y: 对矩阵MM的第x行的每一个数加上y(1≤x≤n,1≤y≤10,000);
4 x y: 对矩阵MM的第x列的每一个数加上y(1≤x≤m,1≤y≤10,000);
2 x y: 交换矩阵MM的第x列和第y列(1≤x,y≤m);
3 x y: 对矩阵MM的第x行的每一个数加上y(1≤x≤n,1≤y≤10,000);
4 x y: 对矩阵MM的第x列的每一个数加上y(1≤x≤m,1≤y≤10,000);
把问题想复杂了,1≤q≤100,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(1≤k≤26)个不同的字母？
比赛时看到子串稍稍有点方,还以为要用字符串的高级算法..然后就跪了
固定左端点,移动右端点,则[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;
}
评论 (0)
