A.Subtraction Game
算法本质
模拟
题目大意
Alice和Bob玩取石子游戏，Alice先取，每回合每个人只能取a或b个石头，无法行动则失败。
规定初始的石子数（大于0），在双方智力在线的情况下，保证Bob能赢。
思路推演
这与传统的取石子游戏有所区别，能取的值只能是a b。
首先想到的就是，能不能让Alice取不了，即<min(a, b)。
若a==1，则考虑选2，这样一人取一个就好。
但是考虑b==2的特殊情况：选3即可。
B.Permutations & Primes
算法本质
思维
题目大意
需要玩家构建长度n的排列p[]，每个区间若其MEX()值为素数，则得分+1。
输出构建最高得分的p[]。
思路推演
素数先枚举几个：2、3、5、7、……
考虑MEX值，而且还是区间考虑，所以基本只用考虑前几个数的位置即可。
首先思考的区间必须包含1，最大化可行区间数，把1放在中间，同时不希望2、3同区间，这样会可能出现4值。
一个朴素的思想——将2、3至于两侧，这样仅有一个区间的值为4。
C.Particles
算法本质
思维
题目大意
给定数组a[]信息，执行若干次操作直到a[]仅剩一个元素：
- 选择某个元素删除，相加合并两侧第一个元素（若在边缘则不合并）
输出最大化的剩余元素值。
思路推演
手动模拟，即可发现元素之间只能合并取决于其奇偶下标，同一奇偶性下标的元素一定能合并。
同时，其奇偶性下标合并时，也可以删除任意元素。
所以只需要相加奇/偶下标的所有正数即可。（若无任何正数，输出最大值即可）
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
inline void solve()
{
cin>>n;
rep(i,1,n) cin>>a[i];
int maxval = *max_element(a+1, a+1+n);
if (maxval <= 0)
{
cout<<maxval<<endl;
return;
}
int sum[2] = {0};
for (int i=1; i<=n; i++)
if (a[i]>0)
sum[i%2] += a[i];
int ans = max(sum[0], sum[1]);
cout<<ans<<endl;
return;
}D.Row Major
算法本质
思维
题目大意
玩家需要构建长度n的小写字母字符串s，保证：
- 若存在
a*b==n，将s从左至右从上至下写入a*b的矩形，保证任意相邻的字符不能相等
输出s。
思路推演
a b即n的约数，每个约数表示两个字符不相等的关系，这是典型的图论。
但是不能用经典图论来做，因为其边数过大。
但是这些边的距离固定，较好计算。
获得n的所有约数，逐个遍历下标，当i下标选择c值时，其i+约数下标无法选择c值，标记一下即可。
（也可以反过来，i下标无法选择i-约数的值）
这时可以发现，所有的字符都是与相同距离的字符存在不相等关系（约数距离），而循环数组通过设定好循环节，完美符合这个要求。
找到最小非n约数值x，因为其非n约数，能保证相邻距离为x的字符无关系——即可以相等。
以x作为循环节，有且仅有相距x倍数的字符相等，符合要求。
（这也解释了26个字母保证有解的原因）ac核心代码 - 朴素做法
头文件、宏定义、快读模板、常见变量、常见变量等略。
int ans[maxn];
bool vis[maxn][30];
inline void solve()
{
cin>>n;
vector<int> v; // 存放约数
for (int i=1; i<=n; i++)
{
if (n%i==0)
v.push_back(i);
fill(vis[i], vis[i]+30, 0); // 清空
}
for (int i=1; i<=n; i++)
{
int val=1;
while (vis[i][val]) // 找到可选的val
val++;
ans[i] = val;
for (int x:v) // 对之后的i+x位置做出限制
if (i+x <= n)
vis[i+x][val] = 1;
}
for (int i=1; i<=n; i++)
cout<<(char)(ans[i]+'a'-1);
cout<<endl;
return;
}ac核心代码 - 极致优化
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
int yue=1;
while (n%yue==0) // 找到第一个非n约数的数，作为循环节长度
yue++;
string ans;
for (int i=1; i<=n; i++)
ans.push_back('a'+i%yue);
cout<<ans<<endl;
return;
}E.Great Grids
算法本质
思维
题目大意
给定n*m的方格，存在3个基础规则：
- 每个方格仅能填
a b c某个字符 - 任意2*2的方格需要包含3个种类的字符
- 任意相邻方格字符不许相同
接下来给定k个特殊要求：
- 每个特殊要求会给定x轴、y轴距离差都为1的两个点，要求这两个点字符一致
判断是否存在满足所有要求的图。
n m k <= 4e3思路推演 - 1 - 需求入手
观察样例，特别是样例4，这意味着特殊要求肯定能产生影响并可传递（不然无法在相对远的地方判断不行）。
所以寻找可传递的影响，然后模拟也可以发现，其传递是通过行列传播的，观察行列传播的特点。
随机选一组数据，向下延申，仅有2种可能：
1 3
3 2
1 3 1 3
3 2 3 2
1 3 2 1继续延申，发现会有重复，其这两列只有：1 3+3 2+2 1这三种情况。
继续模拟研究，发现是最上方的1 3决定的，与主/副对角线相等无关。
称1 3+3 2+2 1为第一组情况，3 1+2 3+1 2为第二组情况，若某行的两列是第一组情况，则任意行的这两列都是第一组情况（只要保证相邻行不重复即可）。
第一组和第二组的区别也可提取出来，即左元素 + x = 右元素。
当某个2*2方格要求主对角线一致时，其行列必须是不同组的情况，反之要求副对角线一致，其行列必须是相同组的情况。
所以可以把i列 i+1列看成a组的点，i行 i+1行看成b组的点，k个要求看作k条边，每条边分别连接ab组点，要求这两个点的值相同或者不同。
检测是否存在满足条件的图。
思路推演 - 2 - 性质入手
给出的多个性质都是2*2的矩形性质，所以可以将其为单位思考，2个2*2之间可以看作其的关系。
将n*m的原矩阵，看作(n-1)*(m-1)的新矩阵。
若主对角线用0表示，副对角线用1表示，新矩阵的2*2仅有4种可能：
01 01 00 00
01 10 00 11若存在0 0 0 1的情况，会失败。
继续模拟，可以发现，若（新矩阵）第一行确定了，则随后的行只能与其值保持一致或者反转（01互换）。
先以每列为点，若某一行的i j列分别有初值：1 0，这表示i j列必然是相反的两列，使用带权并查集标记相反。
依次类推，如果发现冲突则表示不可行。
ac核心代码 - 1 - 需求入手
头文件、宏定义、快读模板、常见变量、常见变量等略。
// 带权并查集板子省略
inline void solve()
{
cin>>n>>m>>k;
flag = 1; // 表示可行
DSU dsu(n+m, 2); // 1~n-1是行代表的点，n+1~n+1+m-1是列代表的点
while (k--)
{
int x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
if (y1 > y2)
{
swap(x1, x2);
swap(y1, y2);
}
int x=x1, y=y1; // 定义2*2的左上角
if (x1>x2) // 副对角线，两者需要相同
{
x--;
if (dsu.same(x, n+y) && dsu.val[x]!=dsu.val[n+y]) // 如果两者已经被保证不同了
flag=0;
dsu.merge(x, n+y, 0);
}
else // 主对角线，两者需要不同
{
if (dsu.same(x, n+y) && dsu.val[x]==dsu.val[n+y])
flag=0;
dsu.merge(x, n+y, 1);
}
}
cout<<(flag ? "YES" : "NO")<<endl;
return;
}ac核心代码 - 2 - 性质入手
头文件、宏定义、快读模板、常见变量、常见变量等略。
// 带权并查集板子省略
写wa了，但是理论是对的，给一篇别人的https://zhuanlan.zhihu.com/p/643164860:
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define pb push_back
using namespace std;
const int N = 4e3 + 10;
int par[N];
inline int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
void merge(int x, int y) {
x = find(par[x]), y = find(par[y]);
if(x == y) return ;
par[x] = y;
}
struct node { int x, val; };
signed main() {
if(fopen("yl.in", "r")) {
freopen("yl.in", "r", stdin);
freopen("yl.out", "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while(T --) {
int n, m, k;
cin >> n >> m >> k;
vector<vector<node>> vec(m);
-- n, -- m;
rep(i,1,n << 1) par[i] = i;
int a, b, c, d;
rep(i,1,k) {
cin >> a >> b >> c >> d;
if(a + 1 == c && b + 1 == d) {
vec[b].pb({a, 1});
} else {
vec[d].pb({a, 2});
}
}
rep(i,1,m) {
int sz = vec[i].size();
rep(j,1,sz - 1) {
if(vec[i][j].val == vec[i][0].val) merge(vec[i][0].x, vec[i][j].x), merge(vec[i][0].x + n, vec[i][j].x + n);
else merge(vec[i][0].x, vec[i][j].x + n), merge(vec[i][0].x + n, vec[i][j].x);
}
}
bool flg = true;
rep(i,1,n) {
if(find(i) == find(i + n)) {
flg = false;
break;
}
}
cout << (flg ? "YES" : "NO") << endl;
}
return 0;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)