The 14th Jilin Provincial Collegiate Programming Contest

A. Chord

题目描述：

给出C, C#, D, D#, E, F, F#, G, G#, A, A# , B这12个音符，且是循环的，即12完了以后还有12…

输入三个音符a b c，记d1为音符a和b的距离，d2为音符c和b的距离，如果存在d1 = 3 && d2 = 4，就输出Minor triad，如果存在d1 = 4 && d2 = 3，就输出Major triad,如果都不满足，就输出Dissonance

思路：

用map存下对应的下标，然后用加法取模来判断即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
map<string, int>mp;
string a, b, c;


bool judge(int p, int q, int x, int y, int z){
    int now = x;
    if((now + p) % 12 == y && (now + p + q) % 12 == z){
        return true;
    }
    return false;
}

void work(){
    mp["C"] = 0;mp["C#"] = 1;mp["D"] = 2;mp["D#"] = 3;
    mp["E"] = 4;mp["F"] = 5;mp["F#"] = 6;mp["G"] = 7;
    mp["G#"] = 8;mp["A"] = 9;mp["A#"] = 10;mp["B"] = 11;
    cin >> a >> b >> c;
    int x = mp[a];
    int y = mp[b];
    int z = mp[c];
    if(judge(4, 3, x, y, z))cout << "Major triad\n";
    else if(judge(3, 4, x, y, z))cout << "Minor triad\n";
    else cout << "Dissonance\n";
}

int main(){
    int t;cin >> t;
    while (t--) {
        work();
    }
    return 0;
}

B.Problem Select

题目描述：

输入n个网页URL，形如：http://acm.hit.edu.cn/problemset/1002，1002即为题目编号，升序输出最小的m个题目编号

思路：

按要求提取出题目编号后排序就行

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
string s[MAX];
int tr[MAX];

ll getans(string s){
    ll num = 0;
    for(int i = 0; i < s.size(); ++i){
        num = num * 10 + (s[i] - '0');
    }
    return num;
}

void work(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> s[i];
    }
    for(int i = 1; i <= n; ++i){
        string ans = "";
        for(int j = 33; j < s[i].size(); ++j){
            ans += s[i][j];
        }
        tr[i] = getans(ans);
    }
    sort(tr + 1, tr + 1 + n);
    for(int i = 1; i <= k; ++i)cout << tr[i] << ' ';
    cout << endl;
}


int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

C. String Game

题目描述：

给你两个串，问这这两个串中相同的子序列的数量，模1e9+7

思路：

dp[i][j]表示s的前i个 ,t的前j个，能产生的相同子序列的数量

可以根据子序列是否包含i分成两堆

dp[i][j] += dp[i-1][j] i不在

if(s[i] == t[j])dp[i][j] += dp[i-1][j-1] i在

边界的初始化

dp[i][0]=1表示s的前i个和t的前j个能产生的相同的子序列的数量为1，即空串

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
string s, t;
int dp[5005][1005];

void work(){
    while (cin >> s >> t) {
        int n = (int)s.size();
        int m = (int)t.size();
        s = " " + s;t = " " + t;
        mem(dp, 0);
        for(int i = 0; i <= n; ++i)dp[i][0] = 1;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                dp[i][j] += dp[i - 1][j];
                if(s[i] == t[j])(dp[i][j] += dp[i - 1][j - 1]) %= mod;
            }
        }
        cout << dp[n][m] << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

E. Shorten the Array

题目描述：

给你一个数组a，对于任意相邻的两个大于0的元素a[i],a[i+1],可以将其删掉，替换成a[i]%a[i+1]或a[i+1]%a[i]，问数组长度最短是多少

思路：

很显然，我们可以用最小的数字是最好的，因为最小的数字可以删掉比他大的任何一个数

所以我第一遍直接统计了一下最小的数出现的次数，然后除2向上取整，wa2直接

这是因为会有 2 2 2 2 2 3的情况存在，这个的结果应该是1，而不是3，因为3 % 2 = 1，出现了比2更小的数，那这个数就可以干掉其他的所有的数

所以，我们可以找出最小的数，用其他所有的数去模它，看能不能得到一个非0的数，如果可以，就说明能产生最小的数，我们就可以直接输出1，否则，我们就输出最小的数字出现的次数除以2向上取整

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1000000 + 50
int n, m;
ll tr[MAX];

int cal(){
    ll minx = *min_element(tr + 1, tr + 1 + n);
    int num = 0;
    for(int i = 1; i <= n; ++i){
        if(tr[i] == minx)++num;
    }
    return (num + 1) / 2;
    
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    ll minx = *min_element(tr + 1, tr + 1 + n);
    for(int i = 1; i <= n; ++i){
        if(tr[i] % minx != 0){
            cout << 1 << endl;
            return;
        }
    }
    cout << cal() << endl;
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

F. Queue

题目描述：

给长度为n的数组ar[i]，m次交换操作l, r

每次交换操作都会将ar[l]与ar[r]进行交换

问这个过程中逆序对的数量最小是多少

思路：

大水题，比赛的时候看过题意，但是没注意数据范围很小可以直接暴力

因为m<=1000, 且r-l<=100,我们可以暴力计算交换后改变的逆序对的数量

对于ar[i], l < i < r，记逆序对数量为ans

如果 ar[i] > ar[l],则++ans

如果ar[i] < ar[l]，则--ans

如果ar[i] > ar[r]，则--ans

如果ar[i] < ar[l]，则++ans

记得判断一下ar[l]和ar[r]

如果ar[l] < ar[r]，则++ans

如果ar[l] > ar[r]，则--ans

记得交换一下那两个值！！！

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define lowbit(x) (x & (-x))
#define MAX 300000 + 50
#define int long long
int n, m, k, op;
int ar[MAX];
int tr[MAX];

inline void insert(int id){
    for(; id <= 100000; id += lowbit(id))++tr[id];
}
inline int getans(int id){
    int ans = 0;
    for(; id; id -= lowbit(id))ans += tr[id];
    return ans;
}

void work(){
    cin >> n;
    mem(tr, 0);
    for(int i = 1; i <= n; ++i){
        cin >> ar[i];++ar[i];
    }
    int num = 0;
    for(int i = 1; i <= n; ++i){
        num += i - 1 -  getans(ar[i]);
        insert(ar[i]);
    }
    cin >> m;
    int l, r;
    int ans = num;
    while (m--) {
        cin >> l >> r;
        if(ar[l] < ar[r])++num;
        if(ar[l] > ar[r])--num;
        for(int i = l + 1; i <= r - 1; ++i){
            if(ar[l] > ar[i])--num;
            if(ar[l] < ar[i])++num;
            if(ar[r] > ar[i])++num;
            if(ar[r] < ar[i])--num;
        }
        swap(ar[l], ar[r]);
        ans = min(ans, num);
    }
    cout << ans << endl;
}


signed main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

G. Matrix

思路：

打表找规律

答案是 sqrt(n) * sqrt(m)

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int t;
ll n, m, k;

void work(){
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        n=(ll)sqrt(n);
        m=(ll)sqrt(m);
        cout << n * m <<endl;
    }
}


int main(){
    work();
    return 0;
}

J. Situation

题目描述：

井字游戏，不过是有初始状态的井字游戏，

先输入一个op，1表示是Alice先下,0表示是Bob先下

再输入一个3 * 3的初始状态的矩阵，.代表还没下,O是Alice下的，X表示是Bob下的

矩阵的最终价值是O的数量减去X的数量，Alice希望这个值尽可能大,Bob希望这个值尽可能小，两个人都聪明秃顶，问最终的价值是多少

思路：

对抗搜索的经典题目，使用min-max搜索

什么是最小最大搜索？就是在决策双方一个希望终值尽可能大，一个希望终值尽可能小的情况下，建立出一棵博弈树，根据子节点的值来确定父节点的值，如下：

从上往下，单数层是我方行动，双数层是对方行动，我方行动需要选择对我最有利的行动，即value大的行动，对方行动则是选择使我方最不利的行动，即value小的行动。

我们需要从最底层第四层开始考虑，双数层所以是对方行动。对于node I，会选择值更小的node M，node I的值更新为0。再考虑第三层，单数层是我方行动。node F会选择I，J中值更大的J，更新为5，G会选择K，L中值更大的L，更新为8。依次一层层向上类推，可以得到最终结果为：

所以这个题，我们可以枚举每个点放O还是X,来获得博弈树，来得到最终答案

因为有T组数组，我们可以开一个记忆化数组记录状态，将3*3的字符数组进行哈希后作为数组的第一维，第二维度记录当前是谁决策

其他的就去爆搜

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
struct ran{
    char tr[5][5];
    int gethaxi(){
        int haxi = 0;
        for(int i = 1; i <= 3; ++i){
            for(int j = 1; j <= 3; ++j){
                if(tr[i][j] == '.')haxi = haxi * 3;
                else if(tr[i][j] == 'O')haxi = haxi * 3 + 1;
                else haxi = haxi * 3 + 2;
            }
        }
        return haxi;
    }
    int fuck(){
        int ans = 0;
        if(tr[1][1] == tr[1][2] && tr[1][2] == tr[1][3] ){
            if(tr[1][1] == 'O')++ans;
            else --ans;
        }
        if(tr[2][1] == tr[2][2] && tr[2][2] == tr[2][3]){
            if(tr[2][1] == 'O')++ans;
            else --ans;
        }
        if(tr[3][1] == tr[3][2] && tr[3][2] == tr[3][3]){
            if(tr[3][1] == 'O')++ans;
            else --ans;
        }
        if(tr[1][1] == tr[2][1] && tr[3][1] == tr[1][1] ){
            if(tr[1][1] == 'O')++ans;
            else --ans;
        }
        if(tr[1][2] == tr[2][2] && tr[3][2] == tr[1][2] ){
            if(tr[1][2] == 'O')++ans;
            else --ans;
        }
        if(tr[1][3] == tr[2][3] && tr[3][3] == tr[1][3] ){
            if(tr[1][3] == 'O')++ans;
            else --ans;
        }
        if(tr[1][1] == tr[2][2] && tr[2][2] == tr[3][3]){
            if(tr[1][1] == 'O')++ans;
            else --ans;
        }
        if(tr[2][2] == tr[1][3] && tr[2][2] == tr[3][1]){
            if(tr[2][2] == 'O')++ans;
            else --ans;
        }
        return ans;
    }
    bool judge(){
        for(int i = 1; i <= 3; ++i){
            for(int j = 1; j <= 3; ++j){
                if(tr[i][j] == '.')return true;
            }
        }
        return false;
    }
};
int dp[MAX][2];
int dfs(ran now, int op){
    int haxi = now.gethaxi();
//    cout << haxi << endl;
    if(dp[haxi][op] != -inf)return dp[haxi][op];
    if(!now.judge())return now.fuck();
    if(op){//max
        for(int i = 1; i <= 3; ++i){
            for(int j = 1; j <= 3; ++j){
                if(now.tr[i][j] == '.'){
                    ran nex = now;
                    nex.tr[i][j] = 'O';
                    dp[haxi][op] = max(dp[haxi][op], dfs(nex, 1 - op));
                }
            }
        }
    }
    else{
        dp[haxi][op] = inf;
        for(int i = 1; i <= 3; ++i){
            for(int j = 1; j <= 3; ++j){
                if(now.tr[i][j] == '.'){
                    ran nex = now;
                    nex.tr[i][j] = 'X';
                    dp[haxi][op] = min(dp[haxi][op], dfs(nex, 1 - op));
                }
            }
        }
    }
    
    return dp[haxi][op];
}


void work(){
    for(int i = 0; i <= 100000; ++i){
        for(int j = 0; j <= 1; ++j){
            dp[i][j] = -inf;
        }
    }
    int t;cin >> t;
    while (t--) {
        int op;cin >> op;
        ran p;
        scanf("%s%s%s", p.tr[1]+1, p.tr[2]+1, p.tr[3]+1);
        cout << dfs(p, op) << endl;
    }
}


int main(){
    work();
    return 0;
}

L. Swimmer

题目描述：

问题可以简化成：给你速度v和时间t以及一个长度为p的泳池，你从0的位置游到p，在从p的位置游回去，一直循环下去，问最终的位置与初始位置的距离是多少

思路：

(v * t) % 2 * p后与p比较大小后分类讨论一下就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1000000 + 50
ll n, m, q;
ll t, id;
ll tr[MAX];

ll cal(ll v, ll t){
    ll ans = v * t;
    ans %= 2 * m;
    if(ans <= m)return ans;
    else return 2 * m - ans;
}

void work(){
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    while (q--) {
        cin >> t >> id;
        cout << cal(tr[id], t) << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

M. Upanishad

题目描述：

求给定区间数字出现偶数次的数字的异或和

思路：

求出现次数为偶数次的数字的异或和 = 出现次数为奇数次的数字的异或和 ^ 出现的数字的异或和

区间出现次数为奇数次的数字的异或和 = 区间异或和(因为出现次数为偶数的异或后就成了0)

关键就在于维护区间出现过的数的异或和

我们可以用一个离散化 + 树状数组来维护

树状数组上插入的是到目前为止每个数最近出现的位置

这样查询的时候我们可以用getans(r) ^ getans(l - 1)来计算答案区间[l, r]中出现的数字的异或和

我们用map来进行离散化同时存储上一次出现这个数字的位置

用pre数组来记录上一次出现这个位置的数字的位置

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define lowbit(x) (x & (-x))
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 500000 + 50
int n, m, k;
int val[MAX];
int sum[MAX];
int pre[MAX];
map<int, int>mp;
struct ran{
    int l, r, id;
    bool operator < (const ran &x)const{
        return r < x.r;
    }
}ar[MAX];
int tr[MAX];
inline void insert(int id, int p){
    for(;id <= n; id += lowbit(id))tr[id] ^= p;
}
inline int getans(int id){
    int ans = 0;
    for(;id;id -= lowbit(id))ans ^= tr[id];
    return ans;
}
int ans[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> val[i];
        sum[i] = sum[i - 1] ^ val[i];
        if(mp[val[i]])pre[i] = mp[val[i]];
        mp[val[i]] = i;
    }
    for(int i = 1; i <= m; ++i){
        cin >> ar[i].l >> ar[i].r;ar[i].id = i;
    }
    sort(ar + 1, ar + 1 + m);
    int now = 1;
    for(int i = 1; i <= m; ++i){
        auto [l, r, id] = ar[i];
        while (now <= r) {
            if(pre[now])insert(pre[now], val[now]);
            insert(now, val[now]);
            ++now;
        }
        ans[id] = getans(r) ^ getans(l - 1) ^ sum[r] ^ sum[l - 1];
    }
    for(int i = 1; i <= m; ++i)cout << ans[i] << endl;
}


int main(){
    io;
    work();
    return 0;
}

总结

A	B	C	D	E	F	G	H	I	J	K	L	M	N
✔️	✔️	✔️		✔️	⌘	✔️			⌘		✔️	⌘

✔️指的是赛时通过
⌘ 值得时赛后补题通过

（这次省赛选拔赛用的是我的电脑Mac，所以我写起来比较顺手，就充当打手，他俩喂我题意，我直接码。后来感觉我这个系统和键盘按键对俩Win队友不是很友好，下次还是用Win吧

上来给我喂了一个B题题意，水题，我就直接写了，但是不小心交到了A题上面，妈的，白增加一次罚时

然后他们俩去做C的DP，我开了另一个签到题L,就直接切了

然后我读了个E，写了一发wa2，yj写了一发C，wa1

然后他改了个边界就过了

我还是一直卡E，能想到把自己hack的样例，但是不知道怎么改

后来发现另一个签到题A题，他俩又喂了一下题意，我写了一下就过了

我和djk还在看E，yj去看G，他打了个表找到了规律，就直接秒了

然后djk去读别的题，我和yj想E，突然想到了可以用所有的数去模最小的数，就可以产生一个更小的数，然后我判了一下就过了

后面就剩两个题，一个博弈J题，一个树状数组M题

赛时花了一个多小时写M题，djk写了个莫队，然后T了，我们俩就优化了很长时间，我也重写了一份，也T，前前后后写了一个多小时，无果

换博弈，随便写了个贪心的思想，结果T了，就下班了

~~结束以后一看M题，题解说出题人特意卡了莫队~~

The 14th Jilin Provincial Collegiate Programming Contest

A. Chord

题目描述：

思路：

B.Problem Select

题目描述：

思路：

C. String Game

题目描述：

思路：

E. Shorten the Array

题目描述：

思路：

F. Queue

题目描述：

思路：

G. Matrix

思路：

J. Situation

题目描述：

思路：

L. Swimmer

题目描述：

思路：

M. Upanishad

题目描述：

思路：

总结

发送评论 编辑评论

推荐文章

发送评论编辑评论