M、A、B、L签到不说。
题目链接:
2018浙江acm省赛

D Sequence Swapping(据说经典模型，做了a才能去做b求最大价值的dp模型

题意：开始的时候读错题意了（我真的是太菜了，学这么多dp，可是都不熟练，啥题都A不掉，菜啊。给一个仅由’(‘与’)’组成的字符串，只有()相连的时候才可以对调位置，每个符号都有其价值，每次移动价值为a[i]*a[i+1],问可以获得的最大价值。
思路：因为第i个括号能获得的最大价值受到第i+1个括号向右移动多少的影响，那么可以得到对于i+1移到右边不同的距离，其第i个移动到一个位置获得的价值有很多种，这里取i+1移动到比i能移动的更右边的最大价值即可。
dp[i][j]表示第i个’字符移到j位置可以获得的最大价值。
那么转移可以为dp[i][j]=dp[i][j]+max(dp[i+1][k]) j

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<memory>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const ll maxn=1e3+7;
const ll mod = 1e9;
char s1[maxn];
ll dp[maxn][maxn];
ll qq[maxn];
int main()
{
    //e满足Note里提到的合法运算式
    //freopen("in.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    ll i,j;
    //ios::sync_with_stdio(false);
    ll T,k,t2,t3,t4,f1,f2,f3,f4;
    ll r,c;
    ll  n,m,K;
    cin >> T;
    ll res;
    while(T--){
    cin >> n;
    cin >> s1;
    memset(dp,0,sizeof(dp));
    ll len1=strlen(s1);
    qq[len1]=qq[len1+1]=0;
    for(i=0;i<len1;i++){
    scanf("%lld",&qq[i]);
    }
    for(i=0;i<len1;i++){
        if(s1[i]=='('){
           res=0;
           for(j=i+1;j<len1;j++){
                if(s1[j]==')')res+=qq[i]*qq[j];
           dp[i][j]=res;
            }
        }
    }
    for(i=len1-1;i>=0;i--){
        res=-1e9;
        for(j=len1-1;j>=i;j--){
        res=max(res,dp[i+1][j]);
        dp[i][j]=dp[i][j]+res;
        }
    }
    ll Max=0;
    for(i=0;i<len1;i++){
    Max=max(Max,dp[0][i]);
    }
    cout << Max << endl;
    }
    return 0;
}

J CONTINUE…?

题意：有n个人，给一个长度为n的01序列，1表示第i个人为男生，0表示第i个人为女生，第i个人拥有价值i的物品，问如何对他们进行分组，使得G1+G3=G2+G4,G1与G2中全为女生，G3与G4中全为男生，如果有分组情况输出分组情况，如果没有直接输出-1。
思路：显然得到一个结论，总价值不为偶数的直接无法满足，那么显然n%4=3或者n%4=0才可以使得结果满足。刚开始相当于把所以女生放在1，把所有男生放在4，问从中拿出哪些男生女生可以使得结果的和为n/2，因为价值是1，2，3，4，。。。n-1，n。那么可以得到如果n%4==0,那么其可以分成n/4对1+n与2+n-1大小的数对，那么只需要把前面的n/4个人与后面的n/4个人分到2与3即可。
如果n%4==3,则相当与把1与(n+1)/2放在左，而(n+1)/2+1放在右。然后剩余的结果又可以%4得到均分。
wa1：超时，memset循环对大数组赋值
源码：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<memory>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <set>
using namespace std;
const int maxn=1e5+7;
typedef long long ll;
struct ttt{
    string s1;
    ll score;
};
ttt q1[maxn];
char s1[maxn];
char s2[maxn];
int main()
{
    //e满足Note里提到的合法运算式
    //freopen("in.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    int i,j;
    int T,k,t1,t2,t3,t4,f1,f2,f3,f4;
    int r,c;
    ll n,m,K;
    t1=0;
    cin >> T;
    while(T--){
    cin >> n;
    cin >> s1;
    if(n%4==1||n%4==2){
        cout << "-1" << endl;continue;
    }
    memset(s2,0,sizeof(s2));
    if(n%4==0){
    t2=n/4;
    for(i=0;i<n;i++){
    j=i+1;
    if(j<=t2||n-i<=t2){
    if(s1[i]=='0')
    s2[i]='1';
    else
    s2[i]='3';
    }else{
    if(s1[i]=='0')
    s2[i]='2';
    else
    s2[i]='4';
    }
    }
    }else{
    t2=(n-3)/4+1;
    t3=(n+1)/2;
    for(i=0;i<n;i++){
    j=i+1;
    if(j<=t2||j==t3||n-i<t2){
    if(s1[i]=='0')
    s2[i]='1';
    else
    s2[i]='3';
    }else{
    if(s1[i]=='0')
    s2[i]='2';
    else
    s2[i]='4';
    }
    }

    }
    cout << s2<< endl;
    }
    return 0;
}

F：Now Loading!!!

题意：

给一个序列的数字a1、a2、a3、a4、a5，然后给n组查询p,问每次p的结果。
思路：由公式可知，只有a[i]改变成p的指数的时候，对应其的b[i](这里b[i]指一个公式对应的一个值。
可以先将p排序从大到小，那么此时是那么可以枚举a的n次方根时候的新a[i]，如果比p大，那么就更新a的结果，然后改变总结果sum即可。这里更新的方法是，枚举a的n次方根，按大到小排序丢入队列，然后丢进去的时候要记录这个a[i]值为第几次方根即可，对于每个p把大于其的全部更新，然后就得出了这个p的对应这个函数的值。
wa1：取mod问题，是对1e9取模，而不是1e9+7，有点想当然了。
wa2：还是取mod问题，不可以ans+=..%mod这样取模
源码：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<memory>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <set>
using namespace std;
const int maxn=5e5+7;
typedef long long ll;
const ll mod = 1e9;
ll q1[maxn];
ll q2[maxn];
struct ttt{
    ll pos,num;
    double key;
    bool operator < (const ttt &b)const{
        return key<b.key;
    }
};
struct tt1{
    ll key;
    ll id;
};
tt1 p[maxn];
ll res[maxn];
int cmp1(tt1 x,tt1 y){ //从大开始慢慢递减
    return x.key>y.key;
}
int main()
{
    //e满足Note里提到的合法运算式
    //freopen("in.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    ll i,j;
    ll T,k,t2,t3,t4,f1,f2,f3,f4;
    ll r,c;
    ll n,m,K;
    double t1;
    double g1,g2,g3,g4,g5;
    cin >> T;
    ll Sum;
    ll Res;
    while(T--){
    cin >> n >> m;
    Sum=0;
    ttt u;
    priority_queue<ttt>G;
    for(i=1;i<=n;i++){
    scanf("%lld",&q1[i]);
    res[i]=1;
    Sum+=q1[i];
    u.key=q1[i];
    u.num=1;
    u.pos=i;
    G.push(u);
    }
    Res=0;
    ll Minp=2e9+7;
    for(i=1;i<=m;i++){
    scanf("%lld",&p[i].key);
    p[i].id=i;

    Minp=min(Minp,p[i].key);
    }
    sort(p+1,p+1+m,cmp1);
    for(i=1;i<=n;i++){
        t1=q1[i];
        u.pos=i;
        for(j=2;j<=35;j++){
            g1=j;
            g2=pow(t1,1.0/g1); //次方根
            if(g2<Minp)break;
            u.key=g2; //key=t1 +1
            u.num=j;
            G.push(u);
        }
    }
    ll gg;
    for(i=1;i<=m;i++){
    while(!G.empty()){
        u=G.top();
        if(u.key>p[i].key){
        gg=floor(q1[u.pos]/res[u.pos]);
        Sum-=gg;
        res[u.pos]=u.num+1;
        gg=floor(q1[u.pos]/res[u.pos]);
        Sum+=gg;
        G.pop();
        }else{
        break;
        }
    }
    Res=(Res+(p[i].id*(Sum%mod))%mod)%mod;
    }
    cout << Res << endl;

    }
    return 0;
}

k:Mahjong Sorting

题意：(题意水题，间接说明了English is important。
给3*m个麻将，玩家将会在这3*m个麻将中选取一个幸运麻将(幸运麻将排在最前面。给n个已经排了序的麻将，问这3*m个麻将中有哪些可能成为幸运的麻将。这里有个门这个麻将，其存在给出的n个麻将中的意义是表明在排序之前，幸运麻将所在的位置。
思路：因为题目给出了排序的方式，那么可以将每个麻将最初的顺序转换为数字的形式去表达。
那么B就是M+Rank,D就是M+M+Rank。那么每个麻将均有一个其排名的数字了，如果第一个数字不是这些数字中最小的，那么说明lucky麻将被选出来了，结果只有一个。如果没被选出来，而结果中没有门这个麻将，那么说明除了这n个以为，所有麻将都有可能被排在第一，当然选出了的第1个也可能，但是选出了的另外n-1个均不可能为lucky麻将。如果有门，那么门左右区间的都可能是lucky麻将，并且如果门前面有且仅一个数字，其也可能是lucky麻将(这里可以参考题目给出的样例
源码：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<memory>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <set>
using namespace std;
const int maxn=2e5+7;
typedef long long ll;
const ll mod = 1e9;
int qq[maxn];
char s1[15];
int main()
{
    //e满足Note里提到的合法运算式
    //freopen("in.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    ll i,j;
    ll T,k,t2,t3,t4,f1,f2,f3,f4;
    ll r,c;
    ll n,m,K;
    double t1;
    double g1,g2,g3,g4,g5;
    cin >> T;
    ll Sum;
    ll Res;
    while(T--){
    cin >> n >> m;
    int pos=0;
    int min1=1e9;
    //memset(qq,0,sizeof(qq));
    for(i=1;i<=n;i++){
    cin >> s1 ;
  //  cout << s1<< endl;
    if(s1[0]=='C'){
    qq[i]=0;

    }else if(s1[0]=='B'){
    qq[i]=m;

    }else if(s1[0]=='D'){
    qq[i]=m+m;

    }else if(s1[0]=='W'){
    pos=i;continue;
    }
    cin >> t2;
    qq[i]+=t2;
    min1=min(min1,qq[i]);
    }

    if(pos==1&&n!=1){
    cout << qq[2] << endl;continue;
    }else if(pos==1){
    cout << m << endl;continue;
    }

    if(min1!=qq[1]){
    cout <<"1"<<endl;continue;
    }
    //cout <<"~666 " << endl;
    if(pos==n){
    cout << 3*m-qq[n-1]+1 << endl;continue;
    }
    t1=0;
    if(pos==2)
    t1=1;
    if(pos==0){
    cout << 3*m-n+1 << endl;continue;
    }else{   //门在中间
    cout << qq[pos+1]-qq[pos-1]+t1-1 << endl;continue;
    }

    }
    return 0;
}