这里写自定义目录标题

1011 Random
1012 Alice and Bob
1002 Dragon slayer
1003 Backpack

1011 Random

题目

在[0,1]随机生成n个数字,并进行m次操作， $\frac{1}{2}$ 的概率删除最大数， $\frac{1}{2}$ 的概率删除最小数。计算剩余数之和的期望值，并对 $10^{9}+7$ 取模。

分析

题目说明为随机数，求期望时即可看成0.5,答案即为 $\frac{n-m}{2}$ ，除数取模可利用逆元进行运算。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=50+5,M=5e5+5;

ll qpow(ll a,ll b) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}

int main() {
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,T;
    cin>>T;
    while(T--) {
        cin>>n>>m;
        cout<<(n-m)*qpow(2,mod-2)%mod<<endl;
    }
    
    return 0;
}

1012 Alice and Bob

题目

有m个0-n之间的数

Alice先手，将当前的数分为两组，Bob选择移除其中一组数，另一组数字全部减1，轮流进行。

当数字中出现0时Alice获胜，当没有数字时Bob获胜

在最优策略情况下，随赢。

分析

可以将每组数字单独分析，将该组数字评分到两组中，其中一组移除，另一组减1，及经过一轮cnt(i)变成了cnt(i-1)/2

,因此倒着遍历，判断cnt(0)>=1即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+5,M=5e5+5;

int a[N];

int main() {
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,T;
    cin>>T;
    while(T--) {
       cin>>n;
       for(int i=0;i<=n;i++) {
            cin>>a[i];
       }
       for(int i=n;i>=1;i--) {
            if(a[i]>=2) a[i-1]+=a[i]/2;
       }
       if(a[0]>=1) printf("Alice\n");
       else printf("Bob\n");
    }

    return 0;
}

1002 Dragon slayer

题目

对于一给定区域，最下角(0,0)，右上角(n,m),起点( ${x_s+0.5,y_s+0.5}$ ),终点是( $x_{t} + 0.5, y_{t} + 0.5$ )

有 k 堵水平或垂直的墙。你可以在区域内的任何方向移动，但不能穿过墙，你可以花费一点体力使墙永久消失。

问至少要耗费多少体力。

1 ≤ n , m , K ≤ 15 1≤n, m, K≤15 1≤n,m,K≤15

分析

可以发现数据范围不大，且对于墙体需要判断是否已经移除，可以通过状态压缩来存储k堵墙的状态。

同时对于地图的处理，可以将地图的线也变为格子，坐标进行响应的变化。

本题可以看做只有边权权0和1的图，可以利用双端队列进行处理。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=50+5,M=5e5+5;

int maze[N][N];
int d[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n,m,k;
int sx,sy,gx,gy;

int bfs() {
    deque<PII> q;
    memset(d,0x3f,sizeof(d));
    q.push_back({sx,sy});
    d[sx][sy]=0;
    while(q.size()) {
        PII t=q.front(); q.pop_front();
        int x=t.first, y=t.second;
        for(int i=0;i<4;i++) {
            int tx=x+dx[i];
            int ty=y+dy[i];
            if(tx<=0||tx>n||ty<=0||ty>m) continue;
            int w=maze[tx][ty];
            if(d[x][y]+w<d[tx][ty]) {
                d[tx][ty]=d[x][y]+w;
                if(w) q.push_back({tx,ty});
                else q.push_front({tx,ty});
            }
        }
    }
    return d[gx][gy]==INF?-1:d[gx][gy];
}

int main() {
    freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    scanf("%d",&T);
    while(T--) {
        memset(maze,0,sizeof(maze));
        scanf("%d%d%d",&n,&m,&k);
        n*=2; m*=2;
        printf("%d %d\n",n,m);
        scanf("%d%d%d%d",&sx,&sy,&gx,&gy);
        sx=sx*2+1; sy=sy*2+1; gx=gx*2+1; gy=gy*2+1;
        int a,b,c,d;
        for(int i=1;i<=k;i++) {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            a*=2; b*=2; c*=2; d*=2;
            if(a==c) {
                int t1=min(b,d),t2=max(b,d);
                for(int j=t1;j<t2;j++) {
                    maze[a][j]=1;
                }
            } else {
                int t1=min(a,c),t2=max(a,c);
                for(int j=t1;j<t2;j++) {
                    maze[j][b]=1;
                }
            }
        }
        int ans=bfs();
        printf("%d\n",ans);
    }
    return 0;
}

1003 Backpack

问题

有n件物品和容量为m的背包，没件物品体积为v，价值为w，求刚好装满背包的物品中价值异或和的最大值，没有则输出-1。

分析

$f_{i,j,k}$ 表示前i个物品，异或和为j，并且体积为k的方案是否存在

则 $f_{i,j,k}$ = $f_{i-1.j,k} | f_{i-1,j⊕w,k-v}$ (选与不选)

可利用bitset实现

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=1e3+50,M=5e5+5;

int ans,w,v,n,m;
bitset<N> f[N],g[N];

int main() {
    // freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    scanf("%d",&T);
    while(T--) {
        for(int i=0;i<N;i++) f[i].reset();
        f[0][0]=1;
        ans=-1;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&v,&w);
            for(int j=0;j<1024;j++) {
                g[j]=f[j];
                g[j]<<=v;
            }
            for(int j=0;j<1024;j++) {
                f[j]|=g[j^w];
            }
        }
        for(int j=0;j<1024;j++){
            if(f[j][m]){
                ans=j;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

2022杭电多校联赛第一场 题解

这里写自定义目录标题

1011 Random

1012 Alice and Bob

1002 Dragon slayer

1003 Backpack

2022杭电多校联赛第一场题解