2021牛客暑期多校训练营1

Problem A. Alice and Bob

题意：告诉你两堆石子的数量，每次可以从一堆拿k（k>0）个且从另一堆那s*k（可为0）个。每个人都采取最优的方法，问最后谁赢。

思路：这个题想了一会就是去找必败态，脑跑找了几组后发现没规律就准备打表，但是找错了一组（14，19），正解应该是（14，20），导致打表都打错了。。。

假设（x,y）是一个必败态，那么可由（x,y）->(x1,y1)就不是必败态，所以由题意可得非必败态就是（x+k,y+s*k）或者（x+s*k，y+k），打表即可。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

const int N = 5e3 + 10;
bool sg[N][N];

int main() {
	//打表
	for (int i = 0; i <= 5000; i++) {
		for (int j = 0; j <= 5000; j++) {
			if (!sg[i][j]) {
				for (int k = 1; k + i <= 5000; k++) {
					for (int s = 0; s * k + j <= 5000; s++) {
						sg[k + i][s * k + j] = 1;
						
					}
				}
				for (int k = 1; k + j <= 5000; k++) {
					for (int s = 0; s * k + i <= 5000; s++) {
						sg[s * k + i][k + j] = 1;
					}
				}
			}
		}
	}
	int t;
	cin >> t;
	int n, m;
	while (t--) {
		cin >> n >> m;
		if (sg[n][m]) cout << "Alice" << endl;
		else cout << "Bob" << endl;
	}
	return 0;
}

Problem B. Ball Dropping

题意：告诉你半径r、上底a、下底b、高度h，问是否会被卡住，否输出Drop，是输出Stuck和圆心到下底的距离。

思路：首先，2*r<b不会被卡住。如果卡住了，我们通过圆心向右做一条辅助线到等腰梯形腰上，并通过相似三角形求出这段长度，再通过相似求出圆心到下底的距离。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
const double eps = 1e-6;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    double r, a, b, h;
    cin >> r >> a >> b >> h;
    if(2*r<b) {
        cout << "Drop" << endl;
    }
    else {
        double c=sqrt((a-b)/2*(a-b)/2+h*h);
        double d = c * r / h;
        double e = d - b / 2;
        double H = h * e / ((a - b) / 2);
        cout << "Stuck" << endl;
        if(H>=eps) printf("%.10lf\n", H);
    }
    return 0;
}

Problem C. Cut the Tree

Problem D. Determine the Photo Position

题意：给你n*n的区域，0代表空位，1代表学生，现在有m个老师，问这m个老师加入这片区域有多少种方法，前提m个老师必须是横着连续一排。

思路：这场的签到题，没啥好说的。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
char a[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= n;j++){
            cin >> a[i][j];
        }
    }
    string s;
    cin >> s;
    ll sum = 0;
    for (int i = 1; i <= n;i++){
        int cnt = 0;
        for (int j = 1; j <= n;j++){
            if(a[i][j]=='1') {
                cnt = 0;
            } 
            else {
                cnt++;
                if(cnt>=m) {
                    sum++;
                }
            }
        }
    }
    
    cout << sum << endl;
    return 0;
}

Problem E. Escape along Water Pipe Problem

Problem F. Find 3-friendly Integers

题意：给你一个区间[L,R]，问这个区间内有多少个数能被3整除或者这个数的子串能被3整除，其中0 mod 3 = 0。

思路：通过观察可以发现当这个数大于等于100那它必定满足题目要求，那么我们只要判断一下小于100的即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t; cin >> t;
    while(t--)
    {
    	ll l, r;
    	cin >> l >> r;
    	ll sum = 0;
    	if(r<=100) 
    	{
      	  for (ll i = l; i <= r;i++) {
        		int temp=i;
        		if(temp%3==0) {
        			sum++;
        			//cout << temp << endl;
        			continue;
				}
        	    while (temp)
        	    {
        	    	if(temp%3==0) {
        	    		sum++;
        	    		break;
					}
        	        ll tmp = i % 10;
        	        if (tmp == 0 || (tmp % 3 == 0))
        	        {
        	            sum++;
        	            //cout << i << endl;
        	            break;
        	        }
        	        temp/=10;
        	    }
        	}
    	}
    else {
        if(l<=100) {
            sum += r - 100;
            for (ll i = l; i <= 100;i++) {
        	int temp=i;
        	if(temp%3==0) {
        			sum++;
        			continue;
				}
            while (temp)
            {
            	if(temp%3==0) {
        	    		sum++;
        	    		break;
					}
                ll tmp = i % 10;
                if (tmp == 0 || (tmp % 3 == 0))
                {
                    sum++;
                    break;
                }
                temp/=10;
            }
        }
        }
        else {
            sum += r - l + 1;
        }
        
    }
    cout << sum << endl;
	}
    
    return 0;
}

Problem G. Game of Swapping Numbers

题意：给你长度为n的序列a和b，你可以任意交换a中两个数k次，问所有ai-bi的绝对值和的最大值是多少。

思路：先去掉绝对值，那ai和bi一定有一正一负，因为是计算绝对值，交换对应的ai和bi不影响他们的结果，所以我们先通过交换优先保证ai>bi，计算出当前差值。然后我们通过对a序列从小到大排序，对b序列从大到小排序，将a中最小的与b中最大的交换位置，此时结果变优了2*(b[i]-a[i])，因为我们相当于改变了他们的符号，从正变负从负变正，所以要乘上2。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
const double eps = 1e-6;
int a[N], b[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] < b[i])
            swap(a[i], b[i]);
        ans += abs(a[i] - b[i]);
    }
    if (n == 2)
    {
        if (k % 2)
            cout << abs(a[1] - b[2]) + abs(a[2] - b[1]) << endl;
        else
            cout << abs(a[1] - b[1]) + abs(a[2] - b[2]) << endl;
        return 0;
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n, greater<int>());
    for (int i = 1; i <= n && i <= k; i++)
    {
        if (b[i] < a[i])
            break;
        ans += 2 * (b[i] - a[i]);
    }
    cout << ans << endl;
    return 0;
}

Problem H. Hash Function

Problem I. Increasing Subsequence

Problem J. Journey among Railway Stations

Problem K. Knowledge Test about Match