题目过于简单,就不在线讲题了,看这个题解即可。

A: 签到题1,记录个id和val,然后再结构体排序,然后用两根指针,一个在前一个在后边输出边移动输出即可,直接计算位置也可以。

#include <bits/stdc++.h>
using namespace std;
struct node{
    int val,id;
    friend bool operator<(const node &a,const node &b){
        return a.val<b.val;
    }
}a[110];
int n;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i].val,a[i].id=i;
    sort(a+1,a+n+1);
    for(int i=1; i<=n/2; i++){
        cout<<a[i].id<<" "<<a[n-i+1].id<<endl;
    }
}

B:签到题2,判断一个括号序列是否合法,典型的栈的应用,见代码。注意下(([[这种trick即可。

string line;
stack <char> s;
bool isok(char a, char b){
    if(a == '(' && b == ')') return true;
    else if(a == '[' && b == ']') return true;
    else return false;
}
int main()
{
    int T; scanf("%d%*c", &T);
    while(T--){
        while(!s.empty()) s.pop();
        char ch;
        while((ch = getchar()) != '\n'){
            if(ch == '(' || ch == '['){
                s.push(ch);
            }
            else if(ch == ')' || ch == ']'){
                if(s.empty()) s.push(ch);
                else if(ch == ']'){
                    if(s.top() != '['){

                    }
                    else{
                        s.pop();
                    }
                }
                else if(ch == ')'){
                    if(s.top() != '('){

                    }
                    else{
                        s.pop();
                    }
                }
            }
        }
        if(s.empty()){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }
    return 0;
}

C:给了n个数,问你能否找到另外一个数使得这n+1个数构成等差数列,有无数个输出-1,没有输出0,否则先输出可以找到的数的个数,然后输出这n个数,一个最简单的想法就是先排序,排序之后我们去找出现的公差的的个数的最大值,发现这个值是>=2的话,显然是无解的,因为存在两种很大跨度的公差添加一个数去平衡,显然是办不到的,接下来就是分类讨论一下,这个值为1, 0的情况了,逻辑严密这题就很好过了。我的代码比较丑,供参考。(PS:反正我没有一发过,我好菜啊)

#include <bits/stdc++.h>
const int maxn = 1e5+10;
int a[maxn];
int b[maxn];
map<int,int>mp;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
        if(n == 1){
            printf("-1\n");
            continue;
        }
        sort(a+1,a+n+1);
        memset(b,0,sizeof(b));
        mp.clear();
        for(int i = 1; i < n; i++) b[i] = a[i+1] - a[i];
        for(int i = 1; i < n; i++) mp[b[i]]++;
        int ans = 0;
        for(map<int,int>::iterator it = mp.begin(); it != mp.end(); it++) ans = max(ans,it->second);
        int add = 1e8;
        for(int i = 1; i < n; i++){
            if(mp[b[i]] == ans){
                add = min(add,b[i]);
            }
        }
        for(int i = 2; i <= n; i++){
            if((a[i] - a[i-1]) != add) cnt++;
        }
        if(cnt >= 2){
            printf("0\n");
            continue;
        }
        else if(cnt == 0){
            if(a[1] == a[2]){
                printf("1\n");
                printf("%d\n",a[1]);
            }
            else if(n >2 ){
                printf("2\n");
                printf("%d %d\n",a[1]-add,a[n]+add);
            }
            else if(n == 2){
                if((a[2] - a[1])%2==1){
                    printf("2\n");
                    printf("%d %d\n",a[1]-add,a[n]+add);
                }
                else{
                    printf("3\n");
                    printf("%d %d %d\n",a[1]-add,(a[1]+a[2])/2,a[2]+add);
                }
            }
        }
        else if(cnt == 1){
            int temp = 0;
            bool flag2 = 1;
            for(int i = 1; i <= n; i++){
                if(a[i] + add != a[i+1]){
                    temp = a[i] + add;
                    if(a[i+1] != temp + add){
                        flag2 = 0;
                    }
                    break;
                }
            }
            if(temp < a[1] || temp > a[n] || flag2 == 0){
                printf("0\n");
            }
            else{
                printf("1\n");
                printf("%d\n",temp);
            }
        }
    }
    return 0;
}

D:这个问题就很有趣了,其实它比C还简单。题意是给定一个集合,该集合由1,2,3….2n组成,n是一个整数。问该集合中有趣子集的数目,答案mod1e9+7。x的子集合有趣定义为,该子集中至少有两个数,a和b,b是a的倍数且a是集合中最小的元素。
分析:考虑一下枚举一个最小元素,那么比它大的元素的个数显然为(2*n / a-1)。这其中的元素有选和不选两种,但是不能全部不选。接下来是所有大于最小元素的元素并且不是最小元素倍数的数,可以随便选,于是公式就很显然了。不嫌麻烦,也可以跑一个快速幂。

int f[2001];  
int main()  
{  
    f[0] = 1;  
    REP2(i, 1, 2000) f[i] = (f[i - 1] << 1) % mod;  
    int n, tt, ks = 0;  
    scanf("%d", &tt);  
    while(tt--){  
        scanf("%d", &n);  
        int ans = 0;  
        REP2(i, 1, n){  
            ans += (1LL * ((f[2 * n / i - 1] - 1) % mod) * 1LL * (f[2 * n - i - 2 * n / i + 1] % mod)) % mod;  
            ans %= mod;  
        }  
        if(ans < 0) ans += mod;  
        printf("Case %d: %d\n", ++ks, ans);  
    }  
    return 0;  
}  

E:题意是给出一个长度为n的序列c[i],每次操作可以删去一个回文子串,求将整个序列删除完需要的最少操作数,n<=500。
分析:区间dp,记dp[i][j]为删完[i,j]这一段的最少操作次数,一种转移是枚举一个k,将这一段分为[i,k]和[k+1,j]两段分别删,那么有dp[i][j]=min(dp[i][k]+dp[k+1][j]),另一种转移是如果满足c[i]==c[j],那么在删完[i+1,j-1]的最后一步时可以顺带把c[i]和c[j]一起删掉,那么有dp[i][j]=min(dp[i-1][j+1]),复杂度O(n^3)

可以用记忆化搜索的方式写,代码1:

int n, c[510], dp[510][510];  
void dfs(int l, int r){  
 if(dp[l][r] < INF) return; 
 if(r <= l){ 
 dp[l][r] = 1; 
 return ; 
 } 
 int tl = l, tr = r; 
 while(tl < tr && c[tl] == c[tr]){ 
 tl++; tr--; 
 dfs(tl, tr); 
 dp[l][r] = min(dp[l][r], dp[tl][tr]); 
 } 
 REP1(k, l, r){ 
 dfs(l, k); 
 dfs(k + 1, r); 
 dp[l][r] = min(dp[l][k] + dp[k + 1][r], dp[l][r]); 
 } 
}  
int main()  
{  
 cin >> n; 
 REP2(i, 1, n) cin >> c[i]; 
 REP1(i, 0, 510){ 
 REP1(j, 0, 510){ 
 dp[i][j] = INF; 
 } 
 } 
 dfs(1, n); 
 cout << dp[1][n] << endl; 
 return 0; 
}  

也可以像昨天讲的区间DP的方式转移,显然递归常数比较大,个人还是推荐这种方式。
代码2:

int n, c[510], dp[510][510];  

int main()  
{  
    cin >> n;  
    for(int i = 1; i <= n; i++) cin >> c[i];  
    for(int i = 1; i < 510; i++){  
        for(int j = 1; j < 510; j++){  
            dp[i][j] = INF;  
        }  
    }  
    for(int i = 1; i <= n; i++) dp[i][i] = 1;  
    for(int len = 2; len <= n; len++){  
        for(int i = 1; i + len - 1 <= n; i++){  
            if(c[i] == c[i + len - 1])  
            {  
                if(len == 2) dp[i][i + 1] = 1;  
                else dp[i][i + len - 1] = min(dp[i + 1][i + len - 2], dp[i][i + len - 1]);  
            }  
            else{  
                dp[i][i + len - 1] = INF;  
            }  
            for(int j = i; j < i + len - 1; j++){  
                dp[i][i + len - 1] = min(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1]);  
            }  
        }  
    }  
    cout << dp[1][n] << endl;  
}