A:

代码：

#include
      
       using namespace std;#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);#define LL long long#define ULL unsigned LL#define fi first#define se second#define pb push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lch(x) tr[x].son[0]#define rch(x) tr[x].son[1]#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair
       
         pll;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL mod =  (int)1e9+7;const int N = 1e5 + 100;int main(){    int T, a, b, c;    scanf("%d", &T);    while(T--){        scanf("%d%d%d", &a, &b, &c);        LL t = a - b;        t = t * (c/2);        if(c&1) t += a;        printf("%I64d\n", t);    }    return 0;}
       
      

 

B：

代码：

#include
      
       using namespace std;#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);#define LL long long#define ULL unsigned LL#define fi first#define se second#define pb push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lch(x) tr[x].son[0]#define rch(x) tr[x].son[1]#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair
       
         pll;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL mod =  (int)1e9+7;const int N = 1e5 + 100;int a[N];int main(){    int n;    scanf("%d", &n);    a[0] = 0; a[n+1] = 0;    for(int i = 1; i <= n; ++i)        scanf("%d", &a[i]);    int ans = 0;    for(int i = 1; i <= n; ++i){        if(a[i-1] == 1 && a[i+1] == 1 && a[i] == 0){            a[i+1] = 0;            ans++;        }    }    printf("%d\n", ans);    return 0;}
       
      

 

C：

题解：模拟， 判断的时候注意 如果是用数组可能会下标越界。

代码：

#include
      
       using namespace std;#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);#define LL long long#define ULL unsigned LL#define fi first#define se second#define pb push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lch(x) tr[x].son[0]#define rch(x) tr[x].son[1]#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair
       
         pll;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL mod =  (int)1e9+7;const int N = 1e6 + 100;int a[N];int vis[N];vector
        
          vc;int main(){    int n;    scanf("%d", &n);    LL sum = 0;    for(int i = 1; i <= n; ++i){        scanf("%d", &a[i]);        ++vis[a[i]];        sum += a[i];    }    for(int i = 1; i <= n; ++i){        sum -= a[i];        --vis[a[i]];        if(sum%2 == 0  && sum/2 < N){            int t = sum/2;            //cout << i <<"  "<< t << endl;            if(vis[t]) vc.pb(i);        }        sum += a[i];        ++vis[a[i]];    }    printf("%d\n", vc.size());    for(auto i : vc){        printf("%d ", i);    }    return 0;}
        
       
      

 

D：

题解：二分次数，然后输出。

代码：

#include
      
       using namespace std;#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);#define LL long long#define ULL unsigned LL#define fi first#define se second#define pb push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lch(x) tr[x].son[0]#define rch(x) tr[x].son[1]#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair
       
         pll;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL mod =  (int)1e9+7;const int N = 1e6 + 100;int a[N];int b[N];int n, k, m = 0;bool check(int x){    int ret = 0;    for(int i = 1; i <= m; ++i){         ret += a[b[i]]/x;    }    return ret >= k;}int main(){    scanf("%d%d", &n, &k);    for(int i = 1, t; i <= n; ++i){        scanf("%d", &t);        ++a[t];    }    for(int i = 1; i < N; ++i){        if(a[i]){            b[++m] = i;        }    }    int l = 1, r = n;    while(l <= r){        int mid = l+r >> 1;        if(check(mid)) l = mid+1;        else r = mid-1;    }    l--;    for(int i = 1, c = 1; c <= k; ){        if(a[b[i]] >= l){            a[b[i]] -= l;            c++;            printf("%d ", b[i]);        }        else i++;    }    return 0;}
       
      

 

E：

题解：将每种类型的话题存在一起， 然后sort一下，把小的排前面，然后跑一下背包就好了。

代码：

#include
      
       using namespace std;#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);#define LL long long#define ULL unsigned LL#define fi first#define se second#define pb push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lch(x) tr[x].son[0]#define rch(x) tr[x].son[1]#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair
       
         pll;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL mod =  (int)1e9+7;const int N = 2e5 + 100;int a[N];int b[N];int dp[N];int main(){    int n;    scanf("%d", &n);    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);    sort(a+1, a+1+n);    int m = 0;    for(int i = 1; i <= n; ++i){        if(a[i] == a[i-1]) b[m]++;        else b[++m] = 1;    }    sort(b+1, b+1+m);    memset(dp, -inf, sizeof(dp));    dp[0] = 0;    for(int i = 1; i <= m; ++i){        for(int j = b[i]; j > 0; --j){            dp[j] = max(dp[j], j);            if(j%2 == 0) dp[j] = max(dp[j], dp[j/2] + j);        }    }    int ans = 0;    for(int i = 1; i < N; ++i)        ans = max(ans, dp[i]);    printf("%d\n", ans);    return 0;}
       
      

 

F：

题解：dp[i][u] 表示 处理到i 之后选了u个点， 他的最大价值是多少。

画画图之后就发现发现，  dp[i][u]  可以从 dp[i - x][u-1] 到 dp[i-1][u-1] 转移过来。

所以对于 dp[i][u] 来说我们需要找到 dp[i-x][u-1] 到 dp[i-1][u-1] 里面的最大值。

 

我一开始是想用线段树搞，写好了之后MLE了......

后来也发现线段树有太多浪费的点了，然后用set， 可能操作太多了， 然后TLE了。。。。。

然后把set改成优先队列就过了，但是跑的太慢了。。。。

最后改成了单调栈， 这个东西不带log 就跑到200ms内了，我一开始是想用这个东西，然后忘了怎么写，就搞了这么多奇奇怪怪的东西。

代码：

#include
      
       using namespace std;#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);#define LL long long#define ULL unsigned LL#define fi first#define se second#define pb push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lch(x) tr[x].son[0]#define rch(x) tr[x].son[1]#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair
       
         pll;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL mod =  (int)1e9+7;const int N = 5100;int a[N];int n, k, x;deque
        
          dq[N];int main(){    scanf("%d%d%d", &n, &k, &x);    for(int i = 1; i <= n; ++i)        scanf("%d", &a[i]);    dq[0].push_back({
    0,0});    LL ans = -1;    for(int i = 1; i <= n; ++i){        for(int j = x-1; j >= 0; --j){            while(!dq[j].empty() && dq[j].front().se < i-k) dq[j].pop_front();            if(dq[j].empty()) continue;            LL val = dq[j].front().fi;            val += a[i];            while(!dq[j+1].empty() && dq[j+1].back().fi <= val) dq[j+1].pop_back();            dq[j+1].push_back({val,i});            if(j+1 == x && i+k > n) ans = max(ans, val);        }    }    printf("%lld\n", ans);    return 0;}