2022 Hangzhou Electric Multi-School 1st Game

C.Backpack

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1024;
ll solve(){
    
    int n,m;
    cin>>n>>m;
    vector<bitset<N>>dp(N);
    // dp ijk 表示前i个物品,The total value is XORedj,总体积为k
    //其中iThe dimensions of the representation are optimized away using rolling arrays
    vector<pair<int,int>>v(N);
    for( int i=0;i<n;i++){
    
        cin>>v[i].first>>v[i].second;
    }
    dp[0][0]=1;
    for( int i=0;i<n;i++){
    
        vector<bitset<N>> ndp=dp;
        for( int j=0;j<N;j++){
    
            ndp[j]|=(dp[j^v[i].second]<<v[i].first);
        }
        dp=ndp;
    }
    for( int i=N-1;i>=0;i--){
    
        if(dp[i][m]) return i;
    }
    return -1;
}
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        cout<<solve()<<"\n";
    }

    system("pause");
}

D.Ball

The meaning of the question is probably from a set of pointsSPick any three points,There are three distance values ​​between these three points,If the median of the three distance values ​​is a prime number,则答案加一.
首先,To determine prime numbers, use a prime number sieve.

If violence is used,枚举三个点,会时间超限.

正确做法是：
首先,枚举两个点,Calculate the line segment determined by all two points,Then sort by the length of the line segments,Use length ordering to reduce time complexity.
Traverse the entire sequence of line segments,Take the current line segment as the median,Left of the current line segment（The length is less than or equal to the current line segment）and take two line segments from the sequence on the right,form an answer.
需要注意的是,The three line segments need to have common endpoints,To maintain endpoints,Just use twobitset,A line segment endpoint that has been visited,The other represents line segment endpoints that have not been visited,The two sets are combined,然后统计1的数量即可.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200100;
vector<int>is_prime(N);
int solve(){
    
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>v(n);
    for( int i=0;i<n;i++){
    
        cin>>v[i].first>>v[i].second;
    }
    vector<array<int,3>>vv;
    for( int i=0;i<n;i++){
    
        for( int j=i+1;j<n;j++){
    
            vv.push_back({
    abs(v[i].first-v[j].first)+abs(v[i].second-v[j].second),i,j});
        }
    }
    sort(vv.begin(),vv.end());
    vector<bitset<2000>>W(2000),B(2000);
    //W[i][j]表示从i到jThe line segment has not been visited
    //B[i][j]表示从i到jThe line segment has been visited
    for( int i=0;i<2000;i++){
    
        W[i].set();
    }   
    int ans=0; 
    for( int i=0;i<vv.size();i++){
    
        int x=vv[i][1],y=vv[i][2];
        if(!is_prime[vv[i][0]]) {
    
            ans+=(W[x]&B[y]).count()+(W[y]&B[x]).count();
        }
        W[x][y]=0;W[y][x]=0;
        B[x][y]=1;B[y][x]=1;
    }
    return ans;


    
}
int main(){
    
    is_prime[1]=1;
    for( int i=2;i<N;i++){
    
        if(is_prime[i]==0){
    
            for( int j=i+i;j<N;j+=i){
    
                is_prime[j]=1;
            }
        }
    }
    int t;
    cin>>t;
    while(t--){
    
        cout<<solve()<<"\n";
    }

    system("pause");
}

H.Path

Use the layered graph method.
Build a layered graph with two layers,The first layer represents that the previous path to the point is not a special path,The second layer represents the previous path to this point is a special path.
If a normal path is read,Then add a path in the first layer and add a path to the first layer in the corresponding position of the second layer.If read in a special path,Then add a path leading to the second layer at the corresponding position of the second layer and add a path leading to the second layer at the corresponding position of the first layer.
除此之外,We also need to consider the direct problem after passing through the special path.对于这个问题,Because of the price0,我们只需要使用一个setMaintenance does not go straight to the point,If the current point is in the second layer of the graph,则遍历set中的所有点,Enqueue points that are not adjacent to the current point.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long 
void solve(){
    
    const int inf=1e18;
    int n,m,s,k;
    cin>>n>>m>>s>>k;
    vector<vector<pair<int,int>>>g(n+n+2);
    auto add=[&](int x,int y,int w,int t){
    
        if(t==0){
    
            g[x].push_back({
    y,w});
            g[x+n].push_back({
    y,w});
        }  
        else {
    
            g[x].push_back({
    y+n,w});
            g[x+n].push_back({
    y+n,w});
        }
    };
    for( int i=0;i<m;i++){
    
        int x,y,w,t;
        cin>>x>>y>>w>>t;
        add(x,y,w,t);
    }
    set<int>unvis;
    for( int i=1;i<=n;i++){
    
        unvis.insert(i);
    }
    vector<int>dis(n+n+1,inf);
    dis[s]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.push({
    0,s});
    while(!q.empty()){
    
        auto cur=q.top();
        q.pop();
        int d=cur.first,x=cur.second;
        if(x>n){
    
            set<int>adj;
            for( auto it:g[x]){
    
                if(it.first>n){
    
                    adj.insert(it.first);           
                    adj.insert(it.first-n);         
                }
                else {
    
                    adj.insert(it.first);
                    adj.insert(it.first+n);
                }
                if(dis[x]+it.second-k<dis[it.first]){
    
                    dis[it.first]=dis[x]+it.second-k;
                    q.push({
    dis[it.first],it.first});
                }
            }
            vector<int>temp;
            for( auto it:unvis){
    
                if(adj.count(it)) {
    
                    continue;
                }
                else if(dis[x]<dis[it]){
    
                    dis[it]=dis[x];
                    q.push({
    dis[it],it});
                }
                temp.push_back(it);
            }
            for( auto it:temp){
    
                unvis.erase(it);
            }

        }
        else{
    
            for( auto it:g[x]){
    
                if(dis[x]+it.second<dis[it.first]){
    
                    dis[it.first]=dis[x]+it.second;
                    q.push({
    dis[it.first],it.first});
                }
            }
        }
    }
    for( int i=1;i<=n;i++){
    
        int ans=min(dis[i],dis[i+n]);
        if(ans==inf){
    
            cout<<-1<<" ";
        }
        else cout<<ans<<" ";
    }
    cout<<"\n";
}
signed main(){
        
    // FILE* file = freopen("out.txt", "w",stdout );
    // FILE* f = freopen("1008.in", "r",stdin );
    int t;
    cin>>t;
    while(t--){
    
        solve();
    }

    system("pause");
}

I.Laser

易知,The entire radar ray range consists of four lines,Then the first point must be on one of the four lines.

1. 首先,Check if all points are collinear with the first point,如果共线,直接返回yes
2. If there is a point that is not collinear with the first point,Then these two points can discuss the center point of the entire radar radiation range,Just violently judge whether the center point meets the requirements.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define x first
// #define y second
struct line
{
    
    int a,b,c;
    line(int a,int b,int c):a(a),b(b),c(c){
    }
    
    pair<int,int>cross(line l){
    
        int d = this->a*l.b-l.a*this->b;
        int x = (this->b*l.c-l.b*this->c)/d;
        int y = (l.a*this->c-this->a*l.c)/d;
        return {
    x,y};
    }
};
int parallel( line x,line y){
    
    return x.a*y.b-x.b*y.a==0;
}
vector<line> get_line(pair<int,int>p){
    
    vector<line>res;
    //ax+by+c==0
    res.push_back(line(0,1,-p.second));
    res.push_back(line(1,0,-p.first));
    res.push_back(line(1,1,-p.first-p.second));
    res.push_back(line(1,-1,p.second-p.first));
    return res;
}
int solve(){
    
    int n;
    cin>>n;
    vector<pair<int,int>>v(n);
    for( int i=0;i<n;i++){
    
        cin>>v[i].first>>v[i].second;    
        // v[i].first*=2;v[i].second*=2;
    }
    auto collinear=[&](pair<int,int>a,pair<int,int>b)->int{
    
        if(a.first==b.first||a.second==b.second||abs(a.first-b.first)==abs(a.second-b.second))
            return true;
        else 
            return false;
    };
    //Check if all points are summedv0共线
    auto check1=[&]()->int{
    
        for( int i=1;i<n;i++){
    
            if(!collinear(v[0],v[i])){
    
                return i; 
            }
        }
        return -1;//都和v0共线
    };
    int x=check1();
    if(x==-1) return true;
    
    auto good=[&](pair<int,int>p){
    
        for( int i=0;i<n;i++){
    
            if(!collinear(p,v[i])) return false;
        }  
        return true;
    };
    //已知v0和x不共线,So discuss these two lines on which line
    auto check2=[&]()->int{
    
        auto xx=get_line(v[x]);
        auto yy=get_line(v[0]);
        for( auto it:xx){
    
            for( auto itt:yy){
    
                if(parallel(it,itt)) continue;
                auto p=it.cross(itt);
                if(good(p)) return true;
            }
        }
        return false;
    };
    return check2();

    
}
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        if(solve()){
    
            cout<<"YES"<<"\n";
        }
        else {
    
            cout<<"NO"<<"\n";
        }
    }

    system("pause");
}

K.Random

Every number left is expected to be0.5,Just take the inverse directly.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1000000007;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    
    if (x < 0) {
    
        x += P;
    }
    if (x >= P) {
    
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, int b) {
    
    T res = 1;
    for (; b; b /= 2, a *= a) {
    
        if (b % 2) {
    
            res *= a;
        }
    }
    return res;
}
struct Z {
    
    int x;
    Z(int x = 0) : x(norm(x)) {
    }
    int val() const {
    
        return x;
    }
    Z operator-() const {
    
        return Z(norm(P - x));
    }
    Z inv() const {
    
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
    
        x = ll(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
    
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
    
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
    
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
    
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
    
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
    
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
    
        Z res = lhs;
        res /= rhs;
        return res;
    }
};
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        int n,m;
        scanf("%d%d",&n,&m);
        if(n==m){
    
            cout<<0<<"\n";
        }
        else {
    
            cout<<(Z(1)/2*(n-m)).val()<<"\n";
        }
    }

    system("pause");
}

L.Alice and Bob

0的数量为1时,is a must win.此外,for all states,若x的数量为n,Then the state can be equivalentn/2个x-1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int solve(){
    
    int n;
    cin>>n;
    vector<int>v(n+1);
    for( int i=0;i<=n;i++){
    
        cin>>v[i];
    }
    for( int i=n;i>0;i--){
    
        v[i-1]+=v[i]/2;
    }
    if(v[0]) return true;
    else return false;

}
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        if(!solve()){
    
            cout<<"Bob"<<"\n";
        }
        else {
    
            cout<<"Alice"<<"\n";
        }
    }

    system("pause");
}