HDU：5670~5764

 

A题： 是一个3进制计数；

1 #include 
      
        2  3 using namespace std; 4  5 int a[100000]; 6  7 int calc(long long n) { 8     int i=0; 9     while(n) {10         a[i++] = n%3;11         n/=3;12     }13     return i;14 }15 16 int main()17 {18     int t;19     cin>>t;20     while(t--) {21         memset(a,0,sizeof(0));22         int m;  //长度23         long long n;24         cin>>m>>n;25         int k = calc(n);26         for(int i=0;i
       
        =0;i--) {30             if(a[i]==0)31                 putchar('R');32             else if(a[i]==1)33                 putchar('G');34             else putchar('B');35         }36         puts("");37     }38     return 0;39 }
       
      

 

B题：矩阵操作，可以线段树，有更好的办法，就是现在的某一行是原来的哪一行记录下来；

1 #include 
      
        2  3 using namespace std; 4  5 const int maxn = 1005; 6 int maps[maxn][maxn]; 7  8 int r[maxn];    //当前的第i 行，是原来的r[i] 9 int c[maxn];10 int addr[maxn]; //当前的第i 行，上面加了addr[i]11 int addc[maxn];12 13 int main()14 {15     int t;16     scanf("%d",&t);17     while(t--) {18         memset(addr,0,sizeof(addr));19         memset(addc,0,sizeof(addc));20 21         int n,m;22         int q;23         scanf("%d%d%d",&n,&m,&q);24         for(int i=0;i
      

 

C题：一个字符串，仅有小写字母，求有多少个子串，至少K个不同的字母；

尺取，最好是hash，map,set可能会超时

1 #include 
      
        2  3 using namespace std; 4  5 const int maxn = 1000000+5; 6  7 char str[maxn]; 8 int vis[300]; 9 10 int main()11 {12     int t;13     cin>>t;14     while(t--) {15         int k;16         scanf("%s%d",str+1,&k);17         int n = strlen(str+1);18         memset(vis,0,sizeof(vis));19         int r=0;20         int cnt=0;21         long long ans = 0;22         for(int l=1;l<=n;l++) {23             while(r
       
        
         =k)29                 ans +=n-r+1;30             if(--vis[str[l]]==0)31                 --cnt;32         }33         cout<
         
          <
         
        
       
      

 

D题：  n秒后，回到原点，有多少不同的路径；

枚举向右走了几步；

公式出来了，大组合数用到乘法逆元，求卡特兰数，在CSUFTOJ中有一个出栈序列的问题，i 步有多少种出栈方式；（代码还没写）