avatar
fireworks99
keep hungry keep foolish

浪潮杯第十届山东省大学生ACM程序设计竞赛

ZOJ题目总链接（4113~4125）

A.Calander

给出一个新的日期计算方法，一周五天（周一至周五），一月6个周（30天），一年有这样的十二个月，给出一个日期及其星期，另给出一个日期，求出星期

总结

一看日期计算 —> 形成思维定式：不就是求两个日期差 % 5吗！

后来各种错：

  1. % 5 之后对应数字为0~4，要搞清楚其对应周几
  2. 封榜后发现与年份无关，一年是那固定的360天，% 5 == 0
  3. 赛后再想想与月份都无关，一个月是那固定的30天， % 5 == 0

所以，题目给出一个新事物（或是旧事物的变式），一定要先找其运行规律，总结特点，抓住特点去做，不要因着急而盲目去做。一个人在敲这个题时，另外两人不仅要思考这方法是否正确、细节是否都注意到了、特判做到了，还要想想是否有更简单的方法，因为更简单的方法一定是更优的，是更能体现参赛者水平的，是出题人想看到的。

Code

#include <map>
#include <cstdio>
#include <iostream>
using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    map<int, string> mp;
    mp[1] = "Monday";
    mp[2] = "Tuesday";
    mp[3] = "Wednesday";
    mp[4] = "Thursday";
    mp[5] = "Friday";
    while(t--)
    {
        int ay, am, ad, by, bm, bd, idx;
        string s;
        scanf("%d%d%d", &ay, &am, &ad);
        cin >> s;
        switch(s[1])
        {
        case 'o':
            idx = 1;
            break;
        case 'u':
            idx = 2;
            break;
        case 'e':
            idx = 3;
            break;
        case 'h':
            idx = 4;
            break;
        case 'r':
            idx = 5;
        }
        scanf("%d%d%d", &by, &bm, &bd);
        int tem = 30 - ad + bd;
        tem %= 5;
        if((idx + tem) % 5 == 0)
            cout << "Friday" << '\n';
        else
            cout << mp[(idx + tem) % 5] << '\n';
    }
    return 0;
}

B.Flipping Game

updating……

C.Wandering Robot

一个机器人按照一个长度为n的指令串重复走k次，求其离原点的最远“折线距离”

总结

第一次我想出一个思路：

执行一次指令串后离原点的距离 * (k - 1) + 最后一次的最优解：WA

研究了一会儿，队友发现：最后一次的最优解可能并不是前（k-1）次位移方向上的！

过了53分钟修改上交：WA

耽误时间长了去看了D题，没敲对，C题int改longlong交了一遍？WA

队友提出利用坐标，发现这种思路跟之前的一样，不过实现起来思路更清晰：WA

队友提出遗漏：答案也可能只是第一次的最优解（比如只执行两次指令时）：AC

  1. 在纸上多画图、多模拟，不至于看不出来第一个错误！

  2. 多思考队友的思路、提出的建议，不要第一时间想着反驳

    （当这题的第一个思路（或主思路）是自己想出来的时候，心里有种不愿别人提出异议的感觉？一种不容别人提出更完善策略的感觉？你的思路跟我的一样，只不过实现方式不一样，我的理应就是对的，即使错了，那你的思路跟我一样必然也是错的）可是你不想想，同一思路换种实现方法可能更清晰呢！

  3. 多质疑自己，将错误的险隘思路拓宽

Code

#include <cmath>
#include <string>
#include <cstdio>
#include <iostream>
using namespace std;

int len;
string s;
long long x, y;

long long cal()
{
    long long ans = 0;
    for(int i = 0; i < len; ++i)
    {
        if(s[i] == 'U')
            y++;
        if(s[i] == 'D')
            y--;
        if(s[i] == 'L')
            x--;
        if(s[i] == 'R')
            x++;
        if(ans < abs(x) + abs(y))
            ans = abs(x) + abs(y);
    }
    return ans;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        cin >> s;
        len = s.length();
        x = 0, y = 0;
        long long first = cal();
        x *= (k - 1);
        y *= (k - 1);
        long long tem = cal();
        cout << max(first, tem) << '\n';
    }
    return 0;
}

D.Game on a Graph

k个分属两阵营的人在一地图上玩游戏，n个点，m条边，每人轮流拿一条边，最后谁拿走便后图不连通了，那个人所在阵营就lose，对面win

总结

信誓旦旦地跟队友说是水题（不过确实是），这题k可以不给出（s.length()自己算），后面m组输入完全用不到。

k个人玩，n个点，只需n-1条边

m条现有边，可以拿走(m - (n - 1)) == m - n + 1条

则下一个人(m - n + 2)所属阵营lose

不过我急于交题去看C，疏忽了，没有%，罚时了

Code

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int k, a, b;
        scanf("%d", &k);
        string s;
        cin >> s;
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i = 0; i < m; ++i)
            scanf("%d%d", &a, &b);
        int tem = (m - n + 2) % k;
        if(tem == 0)
            tem = k;
        if(s[tem - 1] == '1')
            cout << '2' << '\n';
        else
            cout << '1' << '\n';
    }
    return 0;
}

E.

updating……

F.Stones in the Bucket

水题（没有坑）

code

#include <cstdio>
#include <iostream>
using namespace std;

int a[100005];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        long long sum = 0;
        long long ans = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        ans += sum % n;
        int tem = sum / n;
        for(int i = 0; i < n; ++i)
            if(a[i] < tem)
                ans += (tem - a[i]);
        cout << ans << '\n';
    }
    return 0;
}

G.

updating……

H.Tokens on the Segments

这种题应该是经常出现，求最优分配

暴力贪心：

按左界从小到大排序，左界相同按右界从小到大排序

线段从最右向左遍历，每个点也从右向左遍历，相当于“采用了”满足条件的最右点（也是接下来最可能用不到的点）

#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100005;

struct node
{
    int l, r;
} a[N];

bool cmp(node a, node b)
{
    if(a.l != b.l)
        return a.l < b.l;
    else
        return a.r < b.r;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d%d", &a[i].l, &a[i].r);
        sort(a, a + n, cmp);
        map<int, bool> mp;
        int ans = 0;
        for(int i = n - 1; i >= 0; --i)
            for(int j = a[i].r; j >= a[i].l; --j)
                if(!mp[j])
                {
                    mp[j] = 1;
                    ans++;
                    break;
                }
        cout << ans << '\n';
    }
    return 0;
}

I.

updating……

J.

updating……

k.

updating……

L.Median

n个点，m个关系（a > b），求是否可以知道哪些数字可以作为中位数

总结

开场我就看了这题，说好了我从后往前看，结果漏看了M题？！以为有封面吗？！

一眼看去像拓扑排序，但…但是什么呢，忘了当时哪里不明白了，不过后来发现这题可能的中位数不止一个，当时没认识到这一问题

虑中位数的特殊性，中位数意味着一定有n个比它大的，n个比它小的，所以对于1<= x <= n，在给出的关系里寻找比它大数字的个数（入度）的和比它小的数字的个数（出度），只要两者都<= 2/n,就说明可以是中位数

不过最遗憾的是：我明明做过floyd闭包传递（传递闭包的含义指通过传递性推导出尽量多的元素之间的关系 ） https://fireworks99.github.io/2019/04/07/POJ-3660-Cow-Contest/ 在场上却什么也想不出来，还是做少了…

Code of floyd

#include <cstdio>
#include <bitset>
#include <cstring>
#include <iostream>
using namespace std;

int n, m;
bool r[105][105];
int out[105];
int in[105];

void floyd()
{
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(r[i][k] && r[k][j])
                    r[i][j] = 1;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        memset(r, 0, sizeof(r));
        memset(out, 0, sizeof(out));
        memset(in, 0, sizeof(in));
        scanf("%d%d", &n, &m);
        int a, b;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &a, &b);
            r[a][b] = 1;
        }
        floyd();
        bool flag = 1;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
            {
                if(r[i][j] && r[j][i])///r[1][1] == r[1][1] == 1
                {
                    flag = 0;
                    break;
                }
                if(r[i][j])
                {
                    out[i]++;
                    in[j]++;
                }
            }
        if(!flag)
            for(int i = 0; i < n; ++i)
                cout << '0';
        else
        {
            for(int i = 1; i <= n; ++i)
                if(in[i] <= (n >> 1) && out[i] <= (n >> 1))
                    cout << '1';
                else
                    cout << '0';
        }
        cout << '\n';
    }
    return 0;
}

improved Floyd

#include <bitset>

bitset<105> r[105];
void floyd()
{
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(r[j][i])
                    r[j] |= r[i];
}

M.Sekiro

水题，坑：n == 0 n == 1 && k == 1e9

Code

#include <cstdio>
#include <iostream>
using namespace std;


int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        while(k--)
        {
            n = (n + 1) >> 1;
            if(n == 1 || n == 0)
                break;
        }
        cout << n << '\n';
    }
    return 0;
}
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy