A.Sum of Odd Integers
题意：
给定,
，问
是否能被
个互不相同的奇数表示。
题解：
先判断与
的奇偶性，如果奇偶性不同则肯定不行
再判断与
的关系，如果
就可以
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
void solve()
{
ll n, k;
scanf("%lld%lld", &n, &k);
if ((n & 1) != (k & 1))
{
puts("NO");
return;
}
puts((n >= k * k) ? "YES" : "NO");
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
solve();
} B.Princesses and Princes
题意：
给定个公主，每个公主都有自己心仪的王子，按照公主的编号从小到大，每次为她选择她心仪的编号最小的王子，问现在是不是最优匹配，如果不是应该在哪个公主的心仪王子中添加哪个王子。保证王子公主一一配对。
题解：
按公主出现的顺序每次把第一个出现的没有匹配过的王子配对给他，最后扫描一遍所有的公主选出没有匹配的，再扫描一遍所有的王子，如果两者都存在就输出并将两人匹配，否则输出
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
bool p[maxn], pos[maxn];
void solve()
{
int n;
scanf("%d", &n);
memset(pos, 0, sizeof(pos));
for (int i = 1; i <= n; i++)
{
int k;
scanf("%d", &k);
p[i] = 0;
while (k--)
{
int q;
scanf("%d", &q);
if (!p[i] && !pos[q])
{
p[i] = 1;
pos[q] = 1;
}
}
}
for (int i = 1; i <= n; i++)
if (!p[i])
for (int j = 1; j <= n; j++)
if (!pos[j])
{
puts("IMPROVE");
printf("%d %d\n", i, j);
return;
}
puts("OPTIMAL");
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
solve();
} C.Game with Chips（构造）
题意：
有个点，每次操作可以把所有点整体向
,
,
,
移动一格，如果有的点到了边还要移动就会保持不动。问是否可以在
步内完成让每个点经过它的必经之点，如果可以则输出移动序列。
。
题解：
因为给定的最大步数是，所以通过适合的构造方案能保证可以遍历全部格点，具体构造方案如下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
string ans;
ans += string(n - 1, 'D') + string(m - 1, 'R');
for (int i = 0; i < m; i++)
{
ans += string(n - 1, (i & 1) ? 'D' : 'U');
if (i != m - 1)
ans += 'L';
}
cout << ans.size() << endl;
cout << ans << endl;
return 0;
} D.Infinite Path
题意：
给定一个长度为n的排列，位置
的颜色为
。定义一条无穷路径指的是：存在这样一个无穷序列
，该序列对应的每个位置颜色相同；再定义
阶迭代指的是：对每个位置
，进行
次迭代后得到的序列（即
迭代为
，再迭代为
）。询问至少进行几阶迭代后，至少存在一条无穷路径。
题解：
首先很自然的想到从每个到
连一条有向边，那么一定会构成若干个不相交的环。
阶迭代的意思是在每个环中每相邻的
个节点重新组成一个环，那么我们只要对每个环进行判断在数列
的所有环中，能否找到一个等差
，使得环上所有满足等差关系的位置:
等位置的颜色相同，维护这个最小的
就是答案了，这个
就是每个环长度的各个因子，对于每个长度的因子可以
预处理
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
bool vis[maxn];
int p[maxn], c[maxn];
vector<int> d[maxn];
int cal(vector<int> loop)
{
int mn = INF;
for (auto len : d[loop.size()])
{
for (int i = 0; i < len; i++)
{
bool flag = true;
for (int j = i; j < loop.size(); j += len)
{
if (c[loop[i]] != c[loop[j]])
{
flag = false;
break;
}
}
if (flag)
mn = min(mn, len);
}
}
return mn;
}
int main()
{
for (int i = 1; i < maxn; i++)
for (int j = i; j < maxn; j += i)
d[j].push_back(i);
int t;
for (scanf("%d", &t); t >= 1; t--)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &p[i]);
for (int i = 1; i <= n; i++)
{
scanf("%d", &c[i]);
vis[i] = false;
}
int ans = n;
for (int i = 1; i <= n; i++)
{
if (vis[i])
continue;
vector<int> loop;
int k = i;
while (!vis[k])
{
loop.push_back(k);
vis[k] = true;
k = p[k];
}
ans = min(ans, cal(loop));
}
printf("%d\n", ans);
}
return 0;
} E.Count The Blocks
题意：
定义“块”表示连续相同数字的长度。给定，连续写下
这些数，对于每一位数字不够
位的补足前导
，求
长度为
的块有多少个，对
取模。
题解：
打表找规律发现
因此可以发现
或者
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
ll ans[maxn];
int main()
{
int n;
scanf("%d", &n);
ans[1] = 10, ans[2] = 180, ans[3] = 2610;
for (int i = 4; i <= n; i++)
ans[i] = ((20 * ans[i - 1] - 100 * ans[i - 2]) % mod + mod) % mod;
for (int i = n; i >= 1; i--)
printf("%lld ", ans[i]);
puts("");
return 0;
} F.AND Segments
题意：
给定,下面
行，每行给定三个数：
，已知长度为
的序列
满足
，问合法的序列
的数量，
。其中所有数
。
题解：
注意到，考虑枚举每一位来做。我们记录这一位必须为
的区间，可以枚举每个
用差分实现。然后记录必须为
的区间，令
表示最大的
满足
这一段都为
。
的时候考虑：如果
的
，直接
就可以了。如果
的
，说明这个数的这一位不可以为
，考虑
的
，若
，说明它之前没有满足的
，那么
，直接沿用上一个数的方案数。但是若
，说明前面有满足的
，那就必须减去
，相当于
这种思想，然后
。最后根据乘法原理把每一层的
乘起来就行了。
（这题我也没怎么看懂，转自这位博主的题解：链接）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int n, k, m;
int x[maxn], l[maxn], r[maxn];
ll dp[maxn];
int a[maxn], b[maxn];
int main()
{
scanf("%d%d%d", &n, &k, &m);
for (int i = 1; i <= m; ++i)
scanf("%d%d%d", &l[i], &r[i], &x[i]);
ll ans = 1;
dp[0] = 1;
for (int t = 0; t < k; t++)
{
for (int i = 1; i <= n + 1; i++)
a[i] = 0, b[i] = 0;
for (int i = 1; i <= m; i++)
{
if (x[i] >> t & 1)
a[l[i]]++, a[r[i] + 1]--;
else
b[r[i] + 1] = max(b[r[i] + 1], l[i]);
}
for (int i = 1; i <= n + 1; i++)
{
a[i] += a[i - 1];
b[i] = max(b[i], b[i - 1]);
}
for (int i = 1; i <= n + 1; i++)
{
if (!a[i])
{
dp[i] = dp[i - 1];
if (b[i])
dp[i] = (dp[i] - dp[b[i] - 1] + mod) % mod;
}
else
dp[i] = 0;
dp[i] = (dp[i - 1] + dp[i]) % mod;
}
ans = ans * (dp[n + 1] - dp[n] + mod) % mod;
}
cout << ans << endl;
} 
京公网安备 11010502036488号