攜程資格賽B題

好吧，連復賽都沒進，511.。。。

貌似D題是因為沒有用unsigned long long?

括號匹配（二）

描述

給你一個字符串，裡面只包含"(",")","[","]"四種符號，請問你需要至少添加多少個括號才能使這些括號匹配起來。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的

輸入

第一行輸入一個正整數N，表示測試數據組數(N<=10)
每組測試數據都只有一行，是一個字符串S，S中只包含以上所說的四種字符，S的長度不超過100

輸出

對於每組測試數據都輸出一個正整數，表示最少需要添加的括號的數量。每組測試輸出占一行

樣例輸入

4
[]
([])[]
((]
([)]

樣例輸出

0
0
3
2

來源

《算法藝術與信息學競賽》

開始想的是直接暴力搞，不過這樣很多都不會考慮到，匹配括號是一個范圍的匹配問題。會想到區間dp,dp[i][j]代表i到j之間匹配最少需要添加多少符號，如果s[i]==s[j]那麼dp[i][j]=dp[i+1][j-1]，然後隨時更新區間之類的最小值，詳見代碼，dp初始化需要注意。
題目地址：http://acm.nyist.net/JudgeOnline/problem.php?pid=15
AC代碼：

#include
#include
#include
#include
using namespace std;
int dp[105][105];
char s[105];

int main()
{
    int t,i,j,k,l;
    cin>>t;

    while(t--)
    {
        cin>>s;
        int len=strlen(s);
        for(i=0;i






旋轉的二進制
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2119    Accepted Submission(s): 339






Problem Description

給定一個自然數M，及其二進制長度N，得到一個N位的二進制串
    b1  b2  ... bN-1  bN

將該串做左旋轉，即b1移到bN後面，得到一個新的二進制串：
    b2  b3  ... bN-1  bN  b1

對新的二進制串再做左旋轉，得二進制串
    b3  b4  ... bN-1  bN b1  b2

重復旋轉操作操作，可得N個二進制串，對這N個串排序，可得一個N*N的矩陣.
例如：
1 0 0 0 1->0 0 0 1 1->0 0 1 1 0->0 1 1 0 0->1 1 0 0 0
對它們做排序，得矩陣
    0   0   0   1   1
    0   0   1   1   0 
    0   1   1   0   0
    1   0   0   0   1  
    1   1   0   0   0  

問：給出一個自然數M，及其二進制長度N，求出排序矩陣的最後一列。
對於上面的例子，給出M=3，N=5，要你的程序輸出10010。

補充說明：存在自然數M的二進制表達超過N位的情況，在這種情況下，取前N次循環的二進制串排序後的最後一列即可。


 



Input

第一行有一個自然數K，代表有K行測試數據（K<=1000）。
第二行至第K+1行，每行的第一個為自然數M，第二個為二進制長度N(N<64)。



 



Output

輸出K行，每行N個二進制，表示矩陣最後一列從上到下的二進制。



 



Sample Input

3
3 5
4 7
1099512709120 45


 



Sample Output

10010
1000000
110000000000000000000000000000100000000000000


 






還是貼上自己的搓代碼吧，最近好多比賽，一直在水。。。
#include
#include
#include
#include
#include
using namespace std;
char a[1005][1005];
int p[1005];
char res[1005];
char tmp[1005];
unsigned long long m;
int n;
int tt;

int main()
{
	int t,i,j;
	cin>>t;

	while(t--)
    {
        cin>>m>>n;
        tt=n;

        int t=0;
        while(m)
        {
            p[t++]=m&1;
            m>>=1;
        }

        //cout<0;i--)
            {
                a[j][i-1]=a[j-1][i];
            }
            a[j][n-1]=a[j-1][0];
            a[j][n]='\0';
        }

        //cout<0)
                {
                    strcpy(tmp,a[i]);
                    strcpy(a[i],a[j]);
                    strcpy(a[j],tmp);
                }
            }

        for(i=0;i