RC-u1 大家一起查作弊

模拟题

#include<iostream>
#include<cstring>

using namespace std;

int ans = 0,cnt = 0,len = 0;

int main()
{
    string s;
    while(cin>>s){
        //cout<<s<<endl;
        s += " ";
        int cnt1 = 0,cnt2 = 0,cnt3 = 0,cnt4 = 0,i = 0;
        for(int j=0;j<s.length();j++) {
            if(s[j] >= 'a' && s[j] <='z') cnt1 = 1;
            else if(s[j] >= 'A' && s[j] <='Z') cnt2 = 1;
            else if(s[j] >= '0' && s[j] <='9') cnt3 = 1;
            else {
                if(cnt1 == 1 || cnt2 == 1 || cnt3 == 1){
                    cnt++;
                    if(cnt1 == 1 && cnt2 == 1 && cnt3 == 1) ans += 5;
                    else if((cnt1 == 1 || cnt2 == 1) && cnt3 == 1) ans += 3;
                    else if(cnt1 == 1 && cnt2 == 1) ans += 1;
                    cnt1 = 0;cnt2 = 0;cnt3 = 0;
                    len += j - i;
                    //cout<<j-i<<endl;
                }
                i = j + 1;
            }
        }
    }

    cout<< ans << endl;
    cout<< len << " " << cnt;
    return 0;
}

RC-u2 谁进线下了？

模拟 + 优先队列 + 哈希表

import java.util.*;
import java.io.*;

public class Main{
    static BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] alls = new int[31];
    static boolean[] st = new boolean[31];
    static int[] h = {0,25,21,18,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0};
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(bReader.readLine());
        while(n -- > 0) {
            for(int i=0;i<20;i++){
                int a,b;
                String[] strings = bReader.readLine().split(" ");
                a = Integer.parseInt(strings[0]);
                b = Integer.parseInt(strings[1]);
                alls[a] += h[b];
                st[a] = true;
            }
        }
        PriorityQueue<pair> queue = new PriorityQueue<pair>();
        for(int i=1;i<=30;i++) {
            if(st[i]) queue.add(new pair(i, alls[i]));
        }
        while(!queue.isEmpty()) {
            pair pair = queue.poll();
            bWriter.write(pair.x + " " + pair.y + "\n");
        }
        bWriter.flush();
    }
}

class pair implements Comparable<pair>{
    int x,y;

    public pair(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(pair o) {
        if( o.y != y)return o.y - y;
        else return x - o.x;
    }

}

RC-u3 势均力敌

dfs + 状态压缩

被这道题坑死了，二进制枚举的条件弄混淆了，大部分时间都在改这里，最后也没改出来，后面算了一下复杂度24*2^24，以为会超时，就放弃了。结果数据太水，状态压缩也可以过……

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 5,M = 30;
int n,len;
int a[N],d[N],g[M][N];
bool st[N];
int h[N] = {0,0,0,6,24};

void dfs(int u)
{
    if(u == n){
        int t = 0;
        for(int i=0;i<n;i++) g[len][i] = d[i],t = d[i] + t*10; 
        g[len++][n] = t;
        return ;
    }
    for(int i=0;i<n;i++){
        if(!st[i]){
            d[u] = a[i];
            st[i] = true;
            dfs(u+1);
            st[i] = false;
        } 
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans = 0;
    dfs(0);
    for(int i=0;i< 1 << h[n];i++){
        int cnt = 0;
        for(int j=0;j < h[n];j++){
            if(i >> j & 1) cnt++;
        }
        if(cnt == h[n] >> 1){
            int res1 = 0, res2 = 0;
            for(int j = 0;j < h[n];j++) {
                if(i >> j & 1) res1 += g[j][n] * g[j][n];
                else res2 += g[j][n] * g[j][n];
            }
            if(res1 == res2 && res1 != 0){
                ans = i;
                for(int k=0;k<h[n];k++){
                    if(ans>>k&1) cout<<g[k][n]<<endl;
                }
                break;
            }
        }
    }
    return 0;
}

RC-u4 City 不 City

Dijstra + 记录路径

就是一个Dijstra模板并记录最短路径，最后半个小时，不是题看错，就是输出一些很奇怪的答案，最后只得了3分。

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1010,INF = 0x3f3f3f3f;
int n,m,s,t;
int w[N],d[N],g[N][N],p[N];
bool st[N];

void Dijstra()
{
    memset(d,0x3f,sizeof d);
    d[s] = 0;
    while(1)
    {
        int temp = -1;
        for(int i=1;i<=n;i++){
            if(!st[i]&&(temp == -1 || d[temp] > d[i])) temp = i;
        }
        if(temp == -1||temp == t) break;
        st[temp] = true;
        for(int i=1;i<=n;i++){
            if(d[i] > d[temp] + g[temp][i]){
                d[i] = d[temp] + g[temp][i];
                p[i] = temp;
            }else if(d[i] == d[temp] + g[temp][i]){
                int res1 = 0,res2 = 0;
                int t2 = p[i];
                while(t2 != 0){
                    if(p[t2]) res1 = max(res1,w[t2]);
                    t2 = p[t2];
                }
                t2 = temp;
                while(t2 != 0){
                    if(p[t2]) res2 = max(res2,w[t2]);
                    t2 = p[t2];
                }
                //cout<<res1<<" "<<res2<<endl;
                if(res1>res2) p[i] = temp;
            }
        }
    }
    int ans = 0;
    for(int i=p[t];p[i];i=p[i]){
        ans = max(ans,w[i]);
    }
    if(d[t] != INF)cout<<d[t]<<" "<<ans<<endl;
    else cout<<"Impossible";
}

int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=n;i++) cin>>w[i];
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = c;
    }
    Dijstra();
    return 0;
}

RC-u5 贪心消消乐

二维前缀和/一维前缀和

两次前缀和，分别记录分数的前缀和以及黑洞的前缀和，黑洞标记为1，st前缀和不为0，则说明矩阵包含了黑洞，该矩阵无效。

暴力做法-计算每一个矩阵得分，挑选最大值but最后一个点超时

#include<iostream>
#include<cstring> 

using namespace std;

const int N = 110;

int pre[N][N],a[N][N];
int n,cnt,st[N][N],b[N][N];

struct P{
    int x1,y1,x2,y2,score;
}p[N*N];

P tp;

void fill()
{
    int x1 = tp.x1,y1 = tp.y1,x2 = tp.x2,y2 = tp.y2;

    for(int i=x1;i<=x2;i++){
        int h = y2 - y1 + 1;
        // 填充覆盖的区域不可到达 
        for(int j=y1;j<=y2;j++){
            b[i][j] = 1;
        }
        // 方块下移 
        for(int j=y2;j>h;j--){
            swap(a[i][j],a[i][j-h]);
            swap(b[i][j],b[i][j-h]);
        }
    }

    for(int i=1;i<=n;i++){
       for(int j=1;j<=n;j++){
           pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
           st[i][j] = st[i-1][j] + st[i][j-1] - st[i-1][j-1] + b[i][j];
       }
   }
}

int main()
{
   scanf("%d",&n);
   int t,sum = 0;
   for(int i=1;i<=n;i++){
       for(int j=1;j<=n;j++){
           scanf("%d",&t);
           a[j][i] = t;
           if(t == 0) b[j][i] = 1;
           pre[j][i] = pre[j][i-1] + pre[j-1][i] - pre[j-1][i-1] + t;
           st[j][i] = st[j][i-1] + st[j-1][i] - st[j-1][i-1] + b[j][i];
       }
   }

   while(1){
       int res = 0;
       for(int x1=1;x1<=n;x1++){
           for(int y1=1;y1<=n;y1++){
            if(b[x1][y1] == 0) 
               for(int x2=x1;x2<=n;x2++){
                   for(int y2=y1;y2<=n;y2++){
                    if(b[x2][y2] == 0){
                        int t1 = st[x2][y2] - st[x2][y1-1] - st[x1-1][y2] + st[x1-1][y1-1];
                            if(!t1){
                                int t = pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1];
                                if(t>res){
                                    res = t;
                                    tp = {x1,y1,x2,y2,res};
                                }
                            }
                        }else break;
                   }
               }
           }
       }
       if(res > 0){
            p[cnt++] = tp;
            fill();
        }else break;
   }
    for(int i=0;i<cnt;i++){
        int t = p[i].score;
        printf("(%d, %d) (%d, %d) %d\n",p[i].x1,p[i].y1,p[i].x2,p[i].y2,t);
        sum += t;
    }
    printf("%d",sum);
   return 0;
}

一维前缀和，前缀和求每一列的长度，枚举矩阵的上下边界和右边界

#include<iostream>
#include<cstring> 
#include<algorithm>

using namespace std;

const int N = 110;

int pre[N][N],a[N][N];
int n,cnt,st[N][N],b[N][N];

struct P{
    int x1,y1,x2,y2,score;
}p[N*N];

P tp;

bool cmp(const P p1,const P p2){
    if(p1.x1 == p2.x1){
        if(p1.y1 != p2.y1 ) return p2.y1-p1.y1>0;
        else if(p1.x2 != p2.x2) return p2.x2-p1.x2>0;
        else return p2.y2-p1.y2>0;
    }
    else return p2.x1-p1.x1>0;
}

void fill()
{
    int x1 = tp.x1,y1 = tp.y1,x2 = tp.x2,y2 = tp.y2;

    for(int i=x1;i<=x2;i++){
        int h = y2 - y1 + 1;
        // 填充覆盖的区域不可到达 
        for(int j=y1;j<=y2;j++){
            b[i][j] = 1;
        }
        // 方块下移 
        for(int j=y2;j>h;j--){
            swap(a[i][j],a[i][j-h]);
            swap(b[i][j],b[i][j-h]);
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            pre[i][j] = pre[i][j-1] + a[i][j];
            st[i][j] = st[i][j-1] + b[i][j];
        }
    }
}

int main()
{
    scanf("%d",&n);
    int t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&t);
            a[j][i] = t;
            if(t == 0) b[j][i] = 1;
            // 计算每一列的前缀和 
            pre[j][i] = pre[j][i-1] + t;
            st[j][i] = st[j][i-1] + b[j][i];
        }
    }

    while(1){
        int res = 0;
        for(int y1 = 1; y1 <= n; y1++){
            for(int y2 = y1; y2 <= n; y2++){
                int t = 0,t1 = 0,x1 = 1,x2 = 1;
                for(;x2<=n; x2++){
                    t1 += st[x2][y2] - st[x2][y1-1];
                    t += pre[x2][y2] - pre[x2][y1-1];
                    if(t1||t<0) t = 0, t1 = 0, x1 = x2+1;
                    //cout<<t << " "<<t1<<endl;
                    if(t > res){
                        res = t;
                        tp = {x1, y1, x2, y2, res};
                    }else if(t == res&&t!=0){
                        P t2 = {x1,y1,x2,y2,res};
                        if(cmp(t2,tp)) tp = t2;
                    }
                }
            }
        }
        if(res > 0){
            p[cnt++] = tp;
            fill();
        }else break;
    }

    int sum = 0;
    for(int i=0;i<cnt;i++){
        int t = p[i].score;
        printf("(%d, %d) (%d, %d) %d\n",p[i].x1,p[i].y1,p[i].x2,p[i].y2,t);
        sum += t;

    }

    printf("%d",sum);
    return 0;
}