A. 水手又说什么了？

题意： n个城市，每个城市生产一种农产品，要求每种不同的农产品运输到1城市所需要的最大花费

从1城市开始跑dj，然后对同一种农产品的城市最短路取max即可

不理解先了解bfs，最短路算法等

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,k;cin>>n>>m>>k;

    vector<vector<int> > prods(k+1);
    vector<vector<int> > roads(n+1);
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        prods[a].push_back(i);
    }
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        roads[u].push_back(v);
        roads[v].push_back(u);
    }

    vector<int> min_road(n+1,-1);
    queue<int> q;
    min_road[1]=0;
    q.push(1);
    while(q.size()){
        int now=q.front();
        for(auto &r:roads[now]){
            if(min_road[r]==-1){
                q.push(r);
                min_road[r]=min_road[now]+1;
            }
        }
        q.pop();
    }
    for(int i=1;i<=k;i++){
        int res=0;
        for(auto &j:prods[i]){
            res=max(res,min_road[j]);
        }
        cout << res << " ";
    }

B.拉电线

如题意模拟

如果到达i点时线长大于80，则找到上一个为0的点放下电力装置，继续模拟即可

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    int newPos=0,length=0,res=0;
    for(int i=0;i<n;i++){
        length+=arr[i]+1;
        if(length>80){
            i=newPos;
            length=0;
            res++;
        }
        if(arr[i]==0){
            newPos=i;
        }
    }
    cout << res;
}

C.简单的字符串问题

回文串如果长度为偶数n，那最短的就是2，奇数就是3，所以直接模拟寻找i-1,i,i+1,这些位置是否能构成回文，输出最短的即可,没有回文就-1

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin >> str;
    int res=-1;
    for(int i=0;i<=str.length()-2;i++){
        if(str[i]==str[i+1]){
            res=2;
            break;
        }
        else if(i<=str.length()-3){
            if(str[i]==str[i+2]){
                res=3;
            }
        }
    }
    cout << res;
}

D.小牛再战

结论：如果n是偶数，且对于每种在数组中出现的数的个数都是偶数，则必输。否则必胜。

证明：

必败情况：对于你的任何操作，你的对手都会进行复制，最终的情况就是你拿走了倒数第二堆，对手拿走最后一堆，你输了

必胜：将必败局面抛给对手，也就是创造一个上述局面，如果可以创造局面就胜利。首先对数组排序，对于数组大小为奇数，易得： $|a1-a2|+|a2-a3|+ \dots |a_{n-2}-a_{n-1}| \leq a_n-1$ ,可以 $1-a_n$ 看成一段，内部割去部分作为间隔填充，多余的直接拿走。同理偶数情况下： $|a_2-a_3|+|a_4-a_5|+\dots |a_{n-2}-a_{n-1}| \leq |a_n-1-a_1|$ ,也就是把 $a_n$ 变成 $a_1$ ,多余的用于填充以及取走。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
const int MOD=998244353;
int main(){
    int N;
    while(cin >> N){
        if(N==0){
            return 0;
        }
        vector<int> arr(101,0);
        for(int i=0;i<N;i++){
            int a;
            cin >> a;
            arr[a]++;
        }
        int win=true;
        for(int i=1;i<=101;i++){
            if(arr[i]%2==1){
                cout << "Win" << endl;
                win=false;
                break;
            }
        }
        if(win){
            cout << "Lose" << endl;
        }
    }
}

A-D copy from 关于在USTL校赛劝诱队友当VTuber未果只得独自出道这事

E. 空洞以太调控装置

假设数组中有a个奇数b个偶数,发射一个射线v，如果v是奇数，则a,b翻转，否则不变。

由于给了n次，我们预设最倒霉的情况，每个数互不相同，我们从 $a_1,a_2$ 开始平衡，那么取 $v=(a_1+a_2)/2$ ,这样操作一次即可让 $abs(a_1-a_2)<=1$ ,对于后面的 $a_3,a_4 \dots a_n$ 最多都可以用n-1次操作平衡，最终结果就是奇偶个数要么不变要么翻转，且任意两个数差值最多为1，那么答案就是 $ab$ ,记得取模.

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef long long ll;

const int INF = 2e18;

void debug()
{
     cout<<"debug"<<endl;
}


class solution
{
    public:
        void solve();
        void ycl();
        solution(){};
};

const int mod = 998244353;

void solution::solve()
{
    int n;cin>>n;
    vector<int>a(n+1);
    int c1=0,c2=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]%2)c1++;
        else c2++;
    }
    cout<<c1*c2%mod<<endl;
    
}


signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T = 1;
    solution AC;
    //AC.ycl();
    //cin>>T;
    while(T --)
    {
        AC.solve();
    }
    return 0;
}

F. 空洞数据收集装置

通过枚举可以发现对于x,y最多可以产生7种可能，set去重


#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    set<int> s;
    for(int i = 2; i <= n; i++){
        int x = a[i];
        int y = a[i - 1];
        s.insert(x);
        s.insert(y);
        int z = x | y;
        s.insert(z);
        s.insert(x ^ y);
        s.insert(0);
        s.insert((x ^ y) ^ z);
        s.insert(x ^ z);
        s.insert(y ^ z);
    }
    cout << s.size() << "\n";
    return 0;
}

题解

A. 水手又说什么了？

题意： n个城市，每个城市生产一种农产品，要求每种不同的农产品运输到1城市所需要的最大花费

从1城市开始跑dj，然后对同一种农产品的城市最短路取max即可

不理解先了解bfs，最短路算法等

B.拉电线

如题意模拟

如果到达i点时线长大于80，则找到上一个为0的点放下电力装置，继续模拟即可

C.简单的字符串问题

回文串如果长度为偶数n，那最短的就是2，奇数就是3，所以直接模拟寻找i-1,i,i+1,这些位置是否能构成回文，输出最短的即可,没有回文就-1

D.小牛再战

结论：如果n是偶数，且对于每种在数组中出现的数的个数都是偶数，则必输。否则必胜。

证明：

必败情况：对于你的任何操作，你的对手都会进行复制，最终的情况就是你拿走了倒数第二堆，对手拿走最后一堆，你输了

A-D copy from 关于在USTL校赛劝诱队友当VTuber未果只得独自出道这事

E. 空洞以太调控装置

假设数组中有a个奇数b个偶数,发射一个射线v，如果v是奇数，则a,b翻转，否则不变。

F. 空洞数据收集装置

通过枚举可以发现对于x,y最多可以产生7种可能，set去重

F. copy from 知乎