2022“杭电杯”中国大学生算法设计超级联赛（1）签到题5题

Solved Pro.ID Title Ratio(Accepted / Submitted)
1001 String 11.88%(125/1052)
1002 Dragon slayer 19.56%(473/2418)
1003 Backpack 14.23%(270/1897)
1004 Ball 15.29%(52/340)
1005 Grammar 12.21%(21/172)
1006 Travel plan 24.18%(22/91)
1007 Treasure 12.93%(38/294)
1008 Path 14.01%(50/357)
1009 Laser 22.58%(280/1240)
1010 Walk 16.67%(4/24)
1011 Random 33.83%(861/2545)
1012 Alice and Bob 11.90%(604/5077)

K. Random

Problem Description
N numbers, randomly generated between [0,1]

Make M operation, 12 probability to delete the maximum value, 12 probability to delete the minimum value

Calculate the sum of expected value module 109+7

Input
Each test contains multiple test cases. The first line contains the number of test cases T(1≤T≤10000). Description of the test cases follows.

The first line of each test case contains two integers n,m

1≤m≤n≤109

Output
For each test case, print one integer — the answer to the problem.

Sample Input
2
2 2
3 1

Sample Output
0
1

Source
2022“杭电杯”中国大学生算法设计超级联赛（1）

题意：

• 给出n,m。n回合每回合随机生成一个（0,1）的数，然后m次操作，每次随机删掉max值或min值，求最后的期望和。

思路：

• 显然就是n个回合的sum期望为（0~n）/2，m次删掉max/min总共删掉为（0~m）/2。
• 所以期望为（n-m）/2，记得逆元和ll。

#include
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;

void exgcd(LL a, LL b, LL &d, LL &x,  LL & y, LL MOD) { if (b==0) { d = a; x = 1; y = 0; } else { exgcd(b, a % b, d, y, x, MOD); y -= x * (a / b); } }
LL inv(LL a, LL MOD) { LL d=0, x=0, y=0; exgcd(a, MOD,  d,  x, y, MOD); return d == 1 ? (x + MOD) % MOD : -1; 

int main(){
    int T;  cin>>T;
    while(T--){
        LL n, m;  cin>>n>>m;
        cout<<(n-m+mod)*inv(2,mod)%mod<<"\n";
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

L. Alice and Bob

Problem Description
Alice and Bob like playing games.

There are m numbers written on the blackboard, all of which are integers between 0 and n.

The rules of the game are as follows:

If there are still numbers on the blackboard, and there are no numbers with value 0 on the blackboard, Alice can divide the remaining numbers on the blackboard into two sets.

Bob chooses one of the sets and erases all numbers in that set. Then subtract all remaining numbers by one.

At any time, if there is a number with a value of 0 on the blackboard, Alice wins; otherwise, if all the numbers on the blackboard are erased, Bob wins.

Please determine who will win the game if both Alice and Bob play the game optimally.

Input
The first line contains an integer T(T≤2000) —the number of test cases.

The first line of each test case contains a single integers n(1≤∑n≤106) .

The second line of each test case contains n+1 integers a0,a1,a2…an(0≤ai≤106,∑ai=m) — there are ai numbers with value i on the blackboard .

Output
For each test case, print “Alice” if Alice will win the game, otherwise print “Bob”.

Sample Input
2
1
0 1
1
0 2

Sample Output
Bob
Alice

题意：

• A和B玩游戏 ，黑板上有和为m的0-n的数字，规则如下。
• 爱丽丝可以将黑板上剩余的数字分成两组。Bob 选择其中一组并擦除该组中的所有数字。然后将所有剩余的数字减一。
• 任何时候，如果在黑板上有一个数值为0，爱丽丝赢了；否则，如果黑板上的所有数字都被擦除，则 Bob 获胜。
• 如果 Alice 和 Bob 都以最佳方式玩游戏，请确定谁将赢得游戏。

思路：

• 将每个数字i转为$2^{n-i}$，那么Alice获胜的条件就是出现$2^n$。
• Bob将数值-1就转为将集合中数字全部乘2，并去掉另一个集合。那么如果Alice分组的时候可以2等分，无论Bob怎么操作，Alice都在向胜利靠近。
• 那么对于Alice来说，每次都要2等分，反向推相当于就是乘2，即初始的数字总要超过2^n才行，这样每次才能$2\ast 2^{n-1}$。
• 因此只需要判断所有数字的2的幂次总和（即$\sum a[i{]}^2$）是否大于$2^n$即可。
  因为n有1e6非常大，所以逆推每次/2加到上一个数去，判断最后是否大于1即可。

//1012
#include
using namespace std;
const int maxn = 1e6+10;
int a[maxn];
int main(){
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        for(int i = 1; i <= n+1; i++)cin>>a[i];
        for(int i = n+1; i >= 2; i--)
            a[i-1]+=a[i]/2;
        if(a[1]>=1)cout<<"Alice\n";
        else cout<<"Bob\n";
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

B. Dragon slayer

Dragon slayer
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1021 Accepted Submission(s): 291

Problem Description
Long, long ago, the dragon captured the princess. In order to save the princess, the hero entered the dragon’s lair.

The dragon’s lair is a rectangle area of length n and width m. The lower left corner is (0,0) and the upper right corner is (n,m).

The position of the hero is (xs+0.5,ys+0.5).

The position of the dragon is (xt+0.5,yt+0.5).

There are some horizontal or vertical walls in the area. The hero can move in any direction within the area, but cannot pass through walls, including the ends of walls.

The hero wants to go where the dragon is, but may be blocked by walls.

Fortunately, heroes have access to special abilities, and each use of a special ability can make a wall disappear forever.

Since using special abilities requires a lot of physical strength, the hero wants to know how many times special abilities need to be used at least on the premise of being able to reach the position of the evil dragon?

Input
The first line contains an integer T(T≤10) —the number of test cases.

The first line of each test case contains 3 integers n,m,K(1≤n,m,K≤15) —length and width of rectangular area, number of walls

The second line of each test case contains 4 integers xs,ys,xt,yt(0≤xs,xt

The next K lines , each line contains 4 integers x1,y1,x2,y2(0≤x1,x2≤n,0≤y1,y2≤m) — indicates the location of the two endpoints of the wall, ensuring that x1=x2 or y1=y2.

Output
For each test case, a line of output contains an integer representing at least the number of times the special ability was required.

Sample Input
2
3 2 2
0 0 2 1
0 1 3 1
1 0 1 2
3 2 2
0 0 2 1
2 1 2 2
1 0 1 1

Sample Output
2
0

Source
2022“杭电杯”中国大学生算法设计超级联赛（1）

题意：

• 给出nm的地图，主角在（sx+0.5,sy+0.5），终点在（ex+0.5，ey+0.5），然后有k堵垂直或水平的墙，求主角到终点最少要拆掉多少堵墙。

思路：

• 一种错误的做法是，直接起点跑终点，记录经过的墙数，因为拆了一堵墙是整个都没了，因此会影响到后面的路径。另一种比较复杂的做法是从起点往终点搜，每个节点开个set记录经过的节点，但是走来走去改了死循环，比较难写。
• 考虑到题目墙的数量只有15，nm只有20，因此可以暴力所有墙拆和不拆的情况，每次看看起点能不能到达终点即可。
• 对于0.5，可以把所以坐标*2进行处理。开始没有初始值没有memset改了好久。

//1002
#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)

int wall[50][50], cnt;
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
int vis[50][50];

int n, m, k;
int sx, sy, tx, ty;
int ans = 1000000;
int sta; //当前拆的墙
void dfs(int x, int y){
    if(x==tx && y==ty){
        int cc = 0;
        int cct = sta;
        while(cct){
            if(cct%2==1)cc++;
            cct>>=1;
        }
        ans = min(ans, cc);
        return ;
    }
    for(int i = 0; i < 4; i++){
        int nx = x+dx[i]*2, ny = y+dy[i]*2;
        if(nx<0||nx>n || ny<0||ny>m)continue;
        int qq = -1;
        if(i<=1 && wall[x][y+dy[i]]!=-1){//y墙壁
            qq = wall[x][y+dy[i]];
        }else if(i>1 && wall[x+dx[i]][y]!=-1){//x墙壁
            qq = wall[x+dx[i]][y];
        }
        if(!vis[nx][ny]){
            if(qq==-1 || ((sta>>qq)&1 == 1)){ //没墙或拆了的
                vis[nx][ny] = 1;
                dfs(nx,ny);
            }
        }
    }
}

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        cin>>n>>m>>k;
        cin>>sx>>sy>>tx>>ty;
        sx*=2;  sx++;  sy*=2;  sy++;
        tx*=2;  tx++;  ty*=2;  ty++;
        memset(wall,-1,sizeof(wall));  cnt = 0;
        for(int i = 1; i <= k; i++){
            int x1, y1, x2, y2;  cin>>x1>>y1>>x2>>y2;
            x1*=2; y1*=2; x2*=2; y2*=2;
            if(x1==x2){
                if(y2<y1)swap(y1,y2);
                for(int j = y1; j <= y2; j++)wall[x1][j] = cnt;
                cnt++;
            }else {
                if(x2<x1)swap(x1,x2);
                for(int j = x1; j <= x2; j++) wall[j][y1] = cnt;
                cnt++;
            }
        }
        n*=2;  m*=2;
        ans = 1000000;
        for(int i = 0; i < (1<<k); i++){
            memset(vis,0,sizeof(vis));
            sta = i;
            dfs(sx,sy);
        }
        cout<<ans<<"\n";
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

I. Laser

Laser
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 879 Accepted Submission(s): 219

Problem Description
There are n enemies on a two-dimensional plane, and the position of the i-th enemy is (xi,yi)

You now have a laser weapon, which you can place on any grid (x,y)(x, y are real numbers) , and the weapon fires a powerful laser that for any real number k, enemies at coordinates (x+k,y),(x,y+k),(x+k,y+k),(x+k,y−k) will be destroyed.

You are now wondering if it is possible to destroy all enemies with only one laser weapon.

Input
The first line of input is a positive integer T(T≤105) representing the number of data cases.

For each case, first line input a positive integer n to represent the position of the enemy.

Next n line, the i-th line inputs two integers xi,yi(−108≤xi,yi≤108) represents the position of the i-th enemy.

The data guarantees that the sum of n for each test case does not exceed 500,000

Output
For each cases, If all enemies can be destroyed with one laser weapon, output “YES“, otherwise output “NO“(not include quotation marks).

Sample Input
2
6
1 1
1 3
2 2
3 1
3 3
3 4
7
1 1
1 3
2 2
3 1
3 3
1 4
3 4

Sample Output
YES
NO

Source
2022“杭电杯”中国大学生算法设计超级联赛（1）

题意：

• 给出n个点，判断平面上是否存在一个点（任意点都行）满足从这个点出发往上下左右和45度斜对角线共八个方向延伸的射线可以覆盖所有的n个点，可以就YES，不行就NO。

思路：

• 首先如果所有点都在同一条水平/竖直/斜线上，那么可以直接输出。
• 假设我们已经确定一个点在水平方向上(米字的一横)，那么随便找一个不在这条直线上的点，用竖线和两条斜线可以与这条线产生三个交点，只需要暴力判断这三个点作为中心点是否合法即可。
• 因为不能确定这个点是否在米字的一横上，但是对于最终的米字，这个点无非就只有四种情况，即垂直水平和两条斜线，因此每次45度旋转一下所有的点（即旋转了最终的米字形），然后按照横线的情况判断一遍即可。

//1009
#include
using namespace std;
const int maxn = 1e6+10;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
int n, a[maxn], b[maxn], x[maxn], y[maxn];

int onmm(int x, int y){ return x==0||y==0||x==y||x+y==0; }
int chk(int xx, int yy){ //(xx,yy)为中心，所有点都在米字上
    for(int i = 1; i <= n; i++) if(!onmm(xx-x[i],yy-y[i]))return 0;
    return 1;
}
int check(){
    int ok = 1;
    for(int i = 2; i <= n; i++){
        if(x[i]==x[1])continue;
        ok = 0;
        if(chk(x[1],y[i]))return 1;//以(x[1],y[i])为中心的米
        if(chk(x[1],y[i]+(x[i]-x[1])))return 1;//两条斜线交点作为米中心
        if(chk(x[1],y[i]-(x[i]-x[1])))return 1;
        break;
    }
    return ok; //所有点都在竖线上
}

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        cin>>n;
        for(int i = 1; i <= n; i++)cin>>a[i]>>b[i];
        //将所有点旋转4次，分别进行判断
        for(int i = 1; i <= n; i++)x[i]=a[i],y[i]=b[i];
        if(check()){cout<<"YES\n"; continue; }
        for(int i = 1; i <= n; i++)x[i]=b[i],y[i]=a[i];
        if(check()){cout<<"YES\n"; continue; }
        for(int i = 1; i <= n; i++)x[i]=a[i]+b[i],y[i]=a[i]-b[i];
        if(check()){cout<<"YES\n"; continue; }
        for(int i = 1; i <= n; i++)x[i]=a[i]-b[i],y[i]=a[i]+b[i];
        if(check()){cout<<"YES\n"; continue; }
        cout<<"NO\n";
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

C. Backpack

Backpack
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1642 Accepted Submission(s): 524

Problem Description
Alice has a backpack of capacity m that she now wants to fill with some items!

Alice has n items, each of which has a volume vi and a value wi.

Can a number of items be selected from n items such that the backpack is exactly full (ie the sum of the volumes equals the backpack capacity)? If so, what is the maximum XOR sum of the values of the items in the backpack when the backpack is full?

Input
The first line contains an integer T(T≤10) —the number of test cases.

The first line of each test case contains 2 integers n,m(1≤n,m<210) —the number of items, the capacity of the backpack.

The next n lines , each line contains 2 integers vi,wi(1≤vi,wi<210) — the volume and value of the item.

Output
For each test case, output a single line, if the backpack cannot be filled, just output a line of “-1”, otherwise output the largest XOR sum.

Sample Input
1
5 4
2 4
1 6
2 2
2 12
1 14

Sample Output
14

Source
2022“杭电杯”中国大学生算法设计超级联赛（1）

题意：

• n个物品，体积为m的背包，每个物品重量wi和价值vi，求刚好体积为m时，价值的最大异或和是多少。

思路：

• 从01背包进行思考，f[i,j]表示前i个物品，体积为j时能获得的最大价值和。
  如果改为前i个物品，体积为j时能获得的最大异或和，发现无法进行转移，因为前面的值会影响后面的状态，不具有无后向性。
• 然后发现考虑到v,w都在1024内，即最终异或和最大也是小于1024的，所以可以加个维度考虑是否存在异或和为j。此时状态f[i,j,k]表示前i个物品，异或和为j，并且体积为k的方案是否存在。
• 然后思考转移，因为异或是可逆的，所不难推出f[i,j,k] = f[i-1,j,k] or f[i-1,j^vi, k-wi]。
• 在考虑滚动数组，转移时f[i,j]实际上就是f[i-1,j]，f[i-1,j^vi, k-wi]实际上就是f[i-1,j]左移wi位，这两位取或运算即可。因此可以用bitset压缩体积的状态进行优化效率。

//1003
#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 1080;
int v[maxn], w[maxn];
bitset<maxn>f[maxn], g[maxn];//f[j]:异或和为j的方案是否存在, f[j][k]状压体积k

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        int n, m;  cin>>n>>m;
        for(int i = 1; i <= n; i++)cin>>v[i]>>w[i]; //体积,价值
        for(int i = 0; i < maxn; i++)f[i].reset();
        f[0][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < 1024; j++){
                g[j] = f[j];  g[j]<<=v[i];
            }
            for(int j = 0; j < 1024; j++){
                f[j] |= g[j^w[i]];
            }
        }
        int ans = -1;
        for(int i = 0; i < 1024; i++){
            if(f[i][m])ans = i;
        }
        cout<<ans<<"\n";
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34