2022年湖南工学院ACM集训第八次周测题解

.Shake It Off.

445人浏览 · 2022-08-12 17:17:00

.Shake It Off. · 2022-08-12 17:17:00 发布

A题怎么又是动规

来源：2022“杭电杯”中国大学生算法设计超级联赛（7）- Triangle Game

考察：博弈论

难度：橙题

分析：
这是一个NIM游戏的变形博弈论。

规律：只有在 (a−1) ^ (b−1) ^ (c-1)!=0 的时候，先手必胜。

证明：对任意的三角形三边 a,b,c ，这里不妨假设 a>=b>=c ，有 b+c>a ，
变形有 b-1 + c-1 >=a-1
为了方便，用 abc 取代公式里的 a-1，b-1，c-1，即 b+c>=a
假设 a ^ b ^ c ! = 0
那么一定存在一个数 x，使得 a ^ (b-x) ^ c = 0 ，即 b−x=a ^ c
又因为 a+c>=a ^ c > = a − c （这就是为什么一开始要 -1，取到>=的原因）
就有 a+c>=b-x>=a-c
可以发现在减掉一个 x之后三条边仍然满足三角形的性质且 a ^ (b-x)^ c = 0
这里证明的是 b+c>a，那么 a+c>b 和 a+b>c 也是类似的证明
那么留给对手的就是一个异或和等于0的状态，对手只会产生两种结果：
1.无法操作，输掉游戏
2.操作到异或和不等于 0 0 0的状态，那么我们就可以重复上面的操作，最终对方会输。
因此在 (a−1) ^ (b−1) ^ (c-1)!=0 是一个必胜状态。

#include <cstdio>

void Solve()
{
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	puts(((a - 1) ^ (b - 1) ^ (c - 1)) ? "Win" : "Lose");
	return ;
}

int main()
{
	int T; scanf("%d", &T);
	while (T--) Solve();
	return 0;
}

B题怎么又是博弈

来源：AtCoder Beginner Contest 183 E - Queen on Grid

考察：dp，前缀和优化

难度：黄题

如果我们考虑暴力，每个点的答案就是该点往左所有的可行点的答案+往上所有可行点的答案+往左上角的对角线上所有可行点的答案，这样复杂度为 O(N^3) ，显然不可取，如果要让复杂度降到 O(N^2) ，就必须要求出三个方向可行点的前缀和，于是我们可以在计算每个点的同时，往它的下方的一个点，右方的一个点和右下方的一个点传递答案，这样就相当于求了一个前缀和，若分别用 x , y , z 数组表示 3 个方向的前缀和的答案，那么状态转移方程即为：
d p [ i ] [ j ] = x [ i ] [ j ] + y [ i ] [ j ] + z [ i ] [ j ]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5;
const ll mod=1e9+7;
ll dp[N][N],x[N][N],y[N][N],z[N][N];
int h,w;
string s;
int main()
{
   cin>>h>>w;
   dp[0][0]=1;
   for(int i=0;i<h;i++){
       cin>>s;
       for(int j=0;j<w;j++){
           if(s[j]=='.') {
               dp[i][j]=(dp[i][j]+x[i][j]+y[i][j]+z[i][j])%mod;
               x[i+1][j]=(dp[i][j]+x[i][j])%mod;
               y[i][j+1]=(dp[i][j]+y[i][j])%mod;
               z[i+1][j+1]=(dp[i][j]+z[i][j])%mod;
           }
       }
   }
   cout<<dp[h-1][w-1];
   return 0;
}

C题怎么又是思维

来源：AtCoder Beginner Contest 204 C - Tour

考察：dfs

难度：橙题

我们可以把这个国家看成一个简单有向无权图，并把每个节点作为起点跑一遍 DFS，计算总共能到达的结点数即可。
总时间复杂度为 O(n^2) 。

#include <cstdio>
#include <vector>
#define maxn 2005
using namespace std;

vector<int> G[maxn];
bool vis[maxn];

int ans;

void dfs(int v)
{
	if(vis[v]) return;
	vis[v] = true, ans ++;
	for(int u: G[v])
		dfs(u);
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		G[--x].push_back(--y);
	}
	ans = 0;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
			vis[j] = false;
		dfs(i);
	}
	printf("%d\n", ans);
	return 0;
}

D题怎么又是深搜

来源：AtCoder Beginner Contest 230 D - Destroyer Takahashi

考察：贪心

难度：橙题

贪心：对于每段线段，当操作位置选在从其所处的最后一个位置向后延伸m位置时，对后面线段的贡献最大。
将所有线段按照末尾位置从小到大排序。

从前往后遍历每条线段：

如果其首位置再在消除的最后位置前面，那么这条线段已经可以被前面线段触发的操作消掉了。跳过。
如果没有，那么从末位置开始，往后的 m-1 个位置上的线段都会被消掉。更新最后位置。

#include<bits/stdc++.h> 

using namespace std;
typedef long long ll;
const int N=1000010;
struct Node {
	int l,r;
}p[N];

bool cmp(Node a,Node b){
	return a.r<b.r;
}

int main(){
	int n,d;
	cin>>n>>d;
	for(int i=1;i<=n;i++) cin>>p[i].l>>p[i].r;
	sort(p+1,p+1+n,cmp);
	int ans=-0x3f3f3f3f;
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(ans+d-1<p[i].l) cnt++,ans=p[i].r;
	}
	cout<<cnt;
}

E题怎么又是贪心

来源：AtCoder Beginner Contest 196 C - Doubled

考察：思维

难度：橙题

给一个 1 到 $10^{12}$ 范围内的数据 N，问区间 [1, N] 之间有几个数字是左右对称。即满足数据 X 的长度为偶数，而且将 X 分为两个长度相同部分，左边的数据和右边的数据相等。例如 1313 这个数据可以分为 13 和 13。

本题如果使用正问题，即从区间 [1, N] 之间暴力枚举每个 X，判断是否满足条件。这样的话，我们需要执行最多 $10^{12}$ 次，哪怕是 O(N) 时间复杂度的算法，本题也是一个超时。

因此我们考虑反问题，即从 1 开始将两个数字 X 合并，看生成的数字是否超过 N。如果超过，则答案为 X-1。这样我们最多需要暴力枚举 $\sqrt{10^{12}}=10^{6}$ 次，这样 O(N) 时间复杂度可以在 1 秒内完成。

#include <bits/stdc++.h>
using namespace std;
long long n;
int main()
{
  cin >> n;
  int ans = 0;
  for (int i = 1; ;i ++ )
    if (stoll(to_string(i) + to_string(i)) <= n)
      ans ++;
    else break;
  cout << ans << "\n";
  return 0;
}

F题怎么又是签到

来源：AtCoder Beginner Contest 248 D - Range Count Query

考察：二分查找

难度：橙题

可用主席树做，但没必要（如果把数据范围改为 $4e6$ ，就把主席树卡掉了）。

开一个二维 $vector<vector<int>> g(200010)$ , $g[i]$ 里存的数字就是 i 在原序列中所有出现的位置。

对于每个查找值为 $x$ 的询问，在 $g[x]$ 内找到第一个大于等于 $l$ 的位置，再找到第一个小于等于 $r$ 的位置

两个位置之间的数字个数就是答案

#include<bits/stdc++.h>
typedef long long ll;
const int N = 2e5+10,M = 2e5+10,INF = 0x3f3f3f3f,mod = 998244353;

std::vector<int> v[N];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n,q;
    std::cin>>n;
    for(int i = 1 ; i <= n ; i++)
    {
        int x;
        std::cin>>x;
        v[x].push_back(i);
    }
    std::cin>>q;
    while(q--)
    {
        int l,r,x;
        std::cin>>l>>r>>x;
        auto it1 = std::lower_bound(v[x].begin(),v[x].end(),l);
        if(it1==v[x].end())
        {
            std::cout<<0<<'\n';
            continue;
        }
        auto it2 = std::upper_bound(v[x].begin(),v[x].end(),r);
        if(it2==v[x].begin())
        {
            std::cout<<0<<'\n';
            continue;
        }
        it2--;
        std::cout<<(it2-it1+1)<<'\n';
    }
    return 0;
}

G题怎么又是二分

来源：AtCoder Beginner Contest 238 A - Exponential or Quadratic

考察：签到

难度：红题

小学生都知道特判一下2、3、4三个数就好了，其他都输出Yes即可

#include<bits/stdc++.h>
#define endl '\n'
#define please return
#define ac 0
typedef long long ll;
const ll mod = 998244353;
const double eps = 1e-6;
using namespace std;
int main() {
	int n;
	cin >> n;
	if (n <= 4 && n > 1) {
		cout << "NO";
	}
	else {
		cout << "YES";
	}
	please ac;
}