2022杭电多校第一场

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个物品，总价值异或为j，总体积为k
    //其中i表示的维度使用滚动数组优化掉
    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

题意大概是从一个点集S中任取三个点，这三个点之间有三个距离值，若三个距离值的中位数是质数，则答案加一。
首先，判断质数使用一个素数筛即可。

如果使用暴力法，枚举三个点，会时间超限。

正确做法是：
首先，枚举两个点，将所有两点确定的线段计算出来，然后按照线段的长短排序，利用长度的有序性来减少时间复杂度。
遍历整个线段的序列，将当前线段作为中位数，当前线段左边（长度小于等于当前线段）和右边的序列中取两条线段，组成一个答案。
需要注意的是，三条线段需要有共同的端点，为了维护端点，只需用两个bitset，一个表示已经访问过的线段端点，另一个表示没有访问过的线段端点，这两个集合相与，然后统计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到j的线段没有被访问过
    //B[i][j]表示从i到j的线段有被访问过
    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

使用分层图方法。
构建一个两层的分层图，第一层代表该点的上一条路径不是特殊路径，第二层代表该点的上一条路径是特殊路径。
如果读入一条普通路径，则在第一层中添加一条路径并在第二层相应位置添加一条通往第一层的路径。如果读入一条特殊路径，则在第二层相应位置添加一条通往第二层的路径并且在第一次层相应位置添加一条通往第二层的路径。
除此之外，我们还需要考虑通过特殊路径后的直达问题。对于这个问题，由于代价为0，我们只需要使用一个set维护没有直达过的点，若当前点在图的第二层时，则遍历set中的所有点，将与当前点不相邻的点入队。

#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

易知，整个雷达射线范围由四条线组成，那么第一个点一定在四条线中的某一条线上。

1. 首先，判断所有点是否与第一个点共线，如果共线，直接返回yes
2. 如果有一个点和第一个点不共线，那么这两个点可以讨论出整个雷达辐射范围的中心点，只需暴力判断中心点是否符合要求即可。

#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;
    };
    //检查是否所有点都和v0共线
    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不共线，那么讨论这两条线在那条线上
    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

每个留下的数期望都是0.5，直接取逆元即可。

#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时，是必胜点。此外，对于所有状态，若x的数量为n，则可以将该状态等价位n/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");
}