记录 CCF CSP 中的一些入门题 （第二题）

20220302-2 CCF CSP

出行计划

这道题的核心是求出当前出行时间时符合条件的所有计划和;

因此可以考虑通过预处理差分数组提前得到各个时间点所有情况的交集.

#include 
#include 
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;

int n, m, k, q;
int go[N], delay[N], sub[N]; // 定义sub数组作为差分数组

vector bor;

void insert(int sub[], int l, int r)
{
    sub[l] += 1, sub[r + 1] -= 1; //求差分操作
}

int main()
{
    cin >> n >> m >> k;
    // 把每一个出行计划的前后时间边界存入border数组;
　　 // 判断一下, 如果最早时间小于0, 则存入0
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d%d", &go[i], &delay[i]);
        go[i] - delay[i] + 1 < 0 ? bor.push_back({0, go[i]}) : bor.push_back({go[i] - delay[i] + 1, go[i]}); 
    }    
    // 将需要预处理的边界数据加入sub数组中
    for (int i = 0; i < n; i ++ ) insert(sub, bor[i].first, bor[i].second); 
    // 求前缀和得到区间交集情况
    for (int i = 0; i < N; i ++ ) sub[i] += sub[i - 1]; 
    // 依次读入询问, 输出对应出行时间的交集数量
    while (cin >> q) printf("%d\n", sub[q + k]); 
    
    return 0;
}

成功通过

201604-2

俄罗斯方块

#include 

using namespace std;
const int N = 20;

int c, m, high = 4; // high表示下落方块形状的高度
int h[N][N], shape[5][5];

int main()
{
    for (int i = 1; i <= 15; i ++ )
        for (int j = 1; j <= 10; j ++ )
            cin >> h[i][j];

    for (int i = 1; i <= 4; i ++ )
        for (int j = 1; j <= 4; j ++ )
            cin >> shape[i][j];

    cin >> c;

    for (int i = 4; i >= 1; i -- )
    {
        bool flag = false;
        for (int j = 1; j <= 4; j ++ )
            if (shape[i][j]) flag = true;
        if (!flag) high --; // 如果形状的最下面一行全为0，那就抹掉这一行
        else break;
    }

    for (int k = 1; k <= 15 - high + 1; k ++ )
    {
        bool f = true;
        for (int i = 1; i <= high; i ++ )
            for (int j = 1; j <= 4; j ++ )
                if (h[k + i - 1][c + j - 1] && shape[i][j]) f = false; // 说明这一行会发生碰撞
        if (f) m = k; // 如果没有碰撞，则记录最大坐标并跳出
        else break;
    }

    for (int i = 1; i <= high; i ++ )
        for (int j = 1; j <= 4; j ++ )
            if (shape[i][j]) h[m + i - 1][c + j - 1] ++; // 填充方块到最正确的位置上

    for (int i = 1; i <= 15; i ++ )
    {
        for (int j = 1; j <= 10; j ++ )
            cout << h[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

201512-2

消除类游戏

#include 

using namespace std;
const int N = 50;

int n, m, q[N][N], dx[2] = {0, 1}, dy[2] = {1, 0};
bool flag[N][N];

void move(int i, int j, int k)
{
    int a = i + dx[k], b = j + dy[k], c = a + dx[k], d = b + dy[k];
    if (c >= 0 && c < n && d >= 0 && d < m && q[i][j] == q[a][b] && q[i][j] == q[c][d]) // 在不越界的情况下连走两步
        flag[i][j] = flag[a][b] = flag[c][d] = true;  // 连续三个相同就全部标记
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < m; j ++ )
            cin >> q[i][j];

    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < m; j ++ )
            for (int k = 0; k < 2; k ++ ) // 枚举,k=0和k=1分别代表往下走和往右走
                move(i, j, k);

    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            if (flag[i][j]) cout << 0 << ' ';
            else cout << q[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;

}

201509-2

日期计算

#include 
using namespace std;

int y, d, month = 1;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main()
{
    cin >> y >> d;
    bool leap = (y % 4 == 0 && y % 100 || y % 400 == 0);
    if (leap) days[2] ++ ;
    while (d > days[month]) d -= days[month ++ ];
    cout << month << endl << d;
    return 0;
}

20150302-2

数字排序

#include 
const int N = 1010;
using namespace std;

int n, p;
int q[N], map[N];

int main()
{
    cin >> n;
    while (cin >> p) map[p] ++ ;
    
    for (int i = 0; i < n; i ++ )
    {
        int max = 0;
        for (int i = 0; i < N; i ++ )
            if (map[i] > map[max]) max = i;
        if (!map[max]) break;
        cout << max << ' ' << map[max] << endl;
        map[max] = 0;
    }
    return 0;
}

201409-2

画图

#include 
#include 
#include 

using namespace std;
const int N = 110;
typedef pair<int, int> PII;

int n, a, b, c, d, res;
int o[N][N];

vector low, up;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> a >> b >> c >> d;
        low.push_back({a, b});
        up.push_back({c, d});
    }
    
    for (int i = 0; i < 100; i ++ )
        for (int j = 0; j < 100; j ++ )
            for (int k = 0; k < n; k ++ )
                if (i >= low[k].first && j >= low[k].second && i < up[k].first && j < up[k].second) o[i][j] ++;
                
    for (int i = 0; i < 100; i ++ )
        for (int j = 0; j < 100; j ++ )
            if (o[i][j]) res ++ ;
    cout << res;
    return 0;
}

201403-2

窗口

#include 
#include 
#include 

using namespace std;
typedef pair<int, int> PII;

int n, m, a, b, c, d;

vector down, up; 
vector<int> pri; // 定义pre数组表示每个编号的优先级，pre的下标越大，里面存放的编号优先级越高

void before(vector<int> &pri, int x) // 定义before函数将对应优先级内的编号提升到最高，其余优先级依次降低
{
    int tmp = pri[x];
    if (x == n - 1) return;
    for (int i = x; i < n - 1; i ++ ) pri[i] = pri[i + 1];
    pri[n - 1] = tmp;
}
int find(vector &down, vector &up, int a, int b) // find函数寻找范围内优先级最高的窗口
{
    for (int i = n - 1; i >= 0; i -- )
        if (a >= down[pri[i]].first && b >= down[pri[i]].second && a <= up[pri[i]].first && b <= up[pri[i]].second)
        {
            before(pri, i); // 窗口顶置
            return pri[n - 1] + 1;
        }
    return 0; // 返回0说明没有点击到窗口
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        cin >> a >> b >> c >> d;
        down.push_back({a, b});
        up.push_back({c, d});
        pri.push_back(i);
    }
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        int res = find(down, up, a, b);
        if (res) cout << res << endl;
        else cout << "IGNORED" << endl;
    }
    return 0;
}

201312-2

ISBN号码

#include 
#include 
using namespace std;

int s, cnt;
char id;

vector<char> is;

int main()
{
    while (cin >> id) is.push_back(id);
    for (int i = 0; i < 12; i ++ ) 
    {
        if (is[i] != '-') s += (++cnt) * (is[i] - '0');
    }

    s %= 11;
    if (is[12] == 'X' && s == 10) puts("Right");
    else if (is[12] - '0' == s) puts("Right");
    else
    {
        for (int i = 0; i < 12; i ++ ) cout << is[i];
        if (s == 10) cout << 'X';
        else cout << s;
    }
    return 0;
}