3-7题解

lzywakaka · 2023-03-10 22:04:51 · 个人记录

A.生活大爆炸石头剪刀布

大模拟

剪刀赢布和蜥蜴人

布赢石头和斯波克

石头赢剪刀和蜥蜴人

蜥蜴人赢布和斯波克

斯波克赢剪刀和石头

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e5+10 , M = 1e6+10 ;

int A[N] , B[N];
int n,m,x,ans;

void solve(){
    int a,b,ans1=0,ans2=0;
    cin >> n >> a >> b;
    for(int i=1;i<=a;i++) cin >> A[i];
    for(int i=1;i<=b;i++) cin >> B[i];
//    for(int i=1;i<=n;i++) {
//        A[i*a+i]=A[i] , B[i*b+i]=B[i];
//    }
    int j=1 , i=1 , cnt=1;
    while(cnt<=n) {
        if(A[j]==0){
            if(B[i]==2 || B[i]==3) ans1++;
            else if(B[i]==1 || B[i]==4) ans2++;
        }
        else if(A[j]==1){
            if(B[i]==3 || B[i]==0) ans1++;
            else if(B[i]==2 || B[i]==4) ans2++;
        }
        else if(A[j]==2){
            if(B[i]==4 || B[i]==1) ans1++;
            else if(B[i]==3 || B[i]==0) ans2++;
        }
        else if(A[j]==3){
            if(B[i]==4 || B[i]==2) ans1++;
            else if(B[i]==0 || B[i]==1) ans2++;
        }
        else{
            if(B[i]==1 || B[i]==0) ans1++;
            else if(B[i]==2 || B[i]==3) ans2++;
        }
        if(j==a) j=1;
        else j++;
        if(i==b) i=1;
        else i++;
        cnt++;
    }
    cout << ans1 << ' ' << ans2 << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}

B.联合权值

遍历每一个点，记录并更新每一个结点的子节点中的最大值和次大值。

对于答案，每个节点的子节点：答案就是每个子节点总和的平方减去每个子节点的平方和

注：记得取模

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e5+10 , M = 1e6+10 , mod = 10007;

int k[N];
int n,m,x,ans,num;

vector<int> v[N];

void solve(){
    cin >> n;
    for(int i=1;i<n;i++) {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=n;i++) cin >> k[i];
    for(int i=1;i<=n;i++) {
        int res1=0 , res2=0 , maxx=0 , max2;
        for(auto & it : v[i]) {
            res1+=k[it]*k[it] , res2+=k[it];
            if(k[it]>=maxx) max2=maxx , maxx=k[it];
            else if(k[it]>=max2) max2=k[it];
        }
        res2=res2*res2-res1;
        ans=max(ans,maxx*max2);
        num=(num+res2)%mod;
    }
    cout << ans << ' ' << num << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}

D.无线网络发射器选址

首先求一个二维前缀和，然后枚举每一个结点，以该节点为矩形中心节点，计算4个边界节点（注意不要越界）

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e5+10 , M = 1e6+10 ;

int g[150][150];
int n,m,d,ans;

void solve(){
   cin >> d >> m;
   map<int , int> mp;
   while(m--) {
       int a,b,c;
       cin >> a >> b >> c;
       g[a+1][b+1]=c;
   }
   for(int i=1;i<=129;i++) {
       for(int j=1;j<=129;j++) {
           g[i][j]=g[i-1][j]+g[i][j-1]-g[i-1][j-1]+g[i][j];
       }
   }
   for(int i=1;i<=129;i++) {
       for(int j=1;j<=129;j++) {
           int x1=max(i-d,(int)1) , y1=max(j-d,(int)1);
           int x2=min(i+d,(int)129) , y2=min(j+d,(int)129);
           int ans=g[x2][y2]-g[x1-1][y2]-g[x2][y1-1]+g[x1-1][y1-1];
           mp[ans]++;
       }
   }
   int ans=0 , num=-1;
   for(auto & it : mp) {
       if(num==-1 || it.first>num) num=it.first , ans=it.second;
   }
   cout << ans << ' ' << num << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}

E.寻找道路

首先反向建边，从终点往回搜一遍。然后遍历一遍数组，对于终点不能走到的点和该点所连接的节点统统标记为true（走过），然后在正向跑一遍dijkstra板子

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#define endl '\n'

using namespace std;

const int N = 1e5+10 , M = 1e6+10 ;

int n,m,x,ans;
int dis[10010];
bool vis[10010] , st[10010];

vector<int> v[10010] , V[10010];

typedef pair<int , int> PII;

void dj(int x){
    memset(dis , 0x3f , sizeof dis);
    priority_queue<PII , vector<PII> , greater<PII>> q;
    q.push({0,x});
    dis[x]=0;
    while(q.size()){
        auto t = q.top();
        q.pop();
        if(vis[t.second]) continue;
        vis[t.second]=1;
        for(auto & it : v[t.second]) {
            if(dis[it] > dis[t.second] + 1) {
                dis[it] = dis[t.second] + 1;
                q.push({dis[it] , it});
            }
        }
    }
}

int dij(int x,int y){
    memset(dis , 0x3f , sizeof dis);
    priority_queue<PII , vector<PII> , greater<PII>> q;
    q.push({0,x});
    dis[x]=0;
    while(q.size()){
        auto t = q.top();
        q.pop();
        if(st[t.second]) continue;
        st[t.second]=1;
        for(auto & it : V[t.second]) {
            if(dis[it] > dis[t.second] + 1) {
                dis[it] = dis[t.second] + 1;
                q.push({dis[it] , it});
            }
        }
    }
    return (dis[y]==0x3f3f3f3f ? -1 : dis[y]);
}

void solve(){
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int a,b;
        cin >> a >> b;
        v[b].push_back(a);
        V[a].push_back(b);
    }
    int a,b;
    cin >> a >> b;
    dj(b);
    for(int i=1;i<=n;i++) {
        if(!vis[i]) {
            st[i]=1;
            for(auto & it : v[i]) st[it]=1;
        }
    }
    cout << dij(a,b) << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}

F.廊桥分配（补题）

首先贪心的求出两个分区分别分配的1到n到个廊桥的答案。将廊桥编号并且每次使用最小的廊桥最后求一次前缀和，求答案直接枚举廊桥数量，飞机优先队列第一维存该飞机离开时间，第二维存该飞机使用的廊桥编号。最后挨个枚举答案并取最大值。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e5+10 , M = 1e6+10 ;

int n,m1,m2,x,ans;
int res1[N],res2[N]; //res[i]代表该分区分得廊桥i可获得的最大停机数量

typedef pair<int , int> PII;

struct node{
    int x,y;
    bool operator < (const node & t) const {
        return x < t.x;
    }
}a[N],b[N];

void check(node * t , int m , int res[]){
    //将廊桥编号并且每次使用最小的廊桥
    //最后求一次前缀和，求答案直接枚举廊桥数量
    //飞机优先队列第一维存该飞机离开时间，第二维存该飞机使用的廊桥编号
    priority_queue<int , vector<int> , greater<int>> l; //廊桥队列
    priority_queue<PII , vector<PII> , greater<PII>> q; //飞机队列
    for(int i=1;i<=n;i++) l.push(i);
    for(int i=1;i<=m;i++) {
        while(q.size() && t[i].x>=q.top().first) {
            l.push(q.top().second); //将不用的廊桥放回廊桥队列
            q.pop();
        }
        if(l.empty()) continue; //廊桥使用完了，飞机只能停外面
        int d=l.top();
        l.pop();
        res[d]++;
        q.push({t[i].y,d}); //分别是该飞机离开时间和使用廊桥编号
    }
    for(int i=1;i<=n;i++) res[i]+=res[i-1];
}

void solve(){
    cin >> n >> m1 >> m2;
    for(int i=1;i<=m1;i++) cin >> a[i].x >> a[i].y;
    for(int i=1;i<=m2;i++) cin >> b[i].x >> b[i].y;
    sort(a+1,a+m1+1);
    sort(b+1,b+m2+1);
    check(a,m1,res1);
    check(b,m2,res2);
    for(int i=0;i<=n;i++) ans=max(ans,res1[i]+res2[n-i]);
    cout << ans << endl;
}

signed main(){
    freopen("airport.in","r",stdin);
    freopen("airport.out","w",stdout);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}

G.格雷码

本题数值爆longlong，要开__int128

思维题：对于给定的k值（我们让k从1开始，所以开始的时候k++）。如果 k > 2的n次方 ，输出1，然后k的位置变为 2的n次方-k+1 ；否则k的位置不变，输出0。最后每次都要n--，因为数字已经减去了一位。

#include <cstdio>
#include <iostream>
#include <algorithm>
#define endl '\n'
#define int unsigned long long

using namespace std;

__int128 n,m,x,ans;

int read(){
    __int128 x = 0 , ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = (x<<3)+(x<<1) + ch-'0' , ch = getchar();
    return x;
}

void solve(){
    n=read() , x=read();
    x++;
    __int128 w=(__int128)1<<n;
    while(n--) {
        bool flag=0;
        if(x>w/2) cout << 1 , flag=1;
        else cout << 0;
        if(flag) x=w-x+1;
        w>>=1;
    }
}

signed main(void) {
    freopen("code.in","r",stdin);
    freopen("code.out","w",stdout);
    solve();
    return 0;
}