Codeforces Round 981 (Div. 3)
故天将降大任于是人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行拂乱其所为，所以动心忍性，曾益其所不能。
A. Sakurako and Kosuke
题意翻译
题目描述
Sakurako 和 Kosuke 在数轴上用一个点玩游戏。这个点初始在数轴原点。二人轮流操作，Sakurako 先。
在第 ii次移动，玩家将这个点向某个方向移动 2×i−1个单位长度。Sakurako 向负方向移动点，而 Kosuke 向正方向。
设该点坐标为 x。
所以游戏开始后就会发生：
- Sakurako 将点沿负方向移动 11 个单位长度，此时 x=−1x=−1；
- Kosuke 将点沿正方向移动 33 个单位长度，此时 x=2x=2；
- Sakurako 将点沿负方向移动 55 个单位长度，此时 x=−3x=−3；
- ⋅⋅⋅⋅⋅⋅
直到 ∣x∣>n 时，他们才会停下。可以证明游戏一定会结束的。
定义赢家是在游戏结束前最后一个移动点的人。
你的任务是找到赢家。
输入格式
第一行一个正整数 t（1≤t≤100），表示 Sakurako 和 Kosuke 玩游戏的次数。
接下来的 t行，每行一个正整数 n（1≤n≤100），含义见上。
输出格式
总共 t行，每行输出每次游戏的赢家。
观察样例即可 。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll t;cin>>t;
while(t--){
ll n;cin>>n;
if(n%2==0)cout<<"Sakurako"<<endl;
else cout<<"Kosuke"<<endl;
}
return 0;
}B. Sakurako and Water
题意翻译
Sakurako 和 Kosuke 发现了一个用 n×n的矩阵表示的山谷，其中高度 ai,j<0的位置是湖泊。
Sakurako 可以通过选择一个正方形区域，并将其主对角线上每个位置的高度增加 1。
你需要计算她最少需要施展多少次操作，才能将所有湖泊变成非负高度。
题目不难，分清主副对角线走向，规律不难找，找同一对角线上最低的湖泊即可，最低湖泊高度大于零也不用管。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll t;cin>>t;
while(t--){
ll n;cin>>n;
vector<vector<ll>> mp(n+1,vector<ll> (n+1,0));
for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)cin>>mp[i][j];
ll sum=0;
//前n条主对角线
for(ll i=1;i<=n;i++){
ll MIN=0;
ll cur=n+1-i;
for(ll j=1;j<=i;j++){
MIN=min(MIN,mp[j][cur]);
cur++;
}
if(MIN<0)sum+=MIN;
}
//剩下n-1条主对角线
for(ll i=2;i<=n;i++){
ll MIN=0;
ll cnt=i;
for(ll j=1;j<=n+1-i;j++){
MIN=min(MIN,mp[cnt][j]);
cnt++;
}
if(MIN<0)sum+=MIN;
}
cout<<abs(sum)<<endl;
}
return 0;
}C. Sakurako's Field Trip
题意翻译
老师让学生排成一列，每个学生的兴趣主题是 ai。干扰是相邻学生兴趣相同的对数，即满足 aj=aj+1的情况数（1≤j<n）。
你可以选择任意学生位置 ii，将其与位置 n−i+1 的学生交换，操作次数不限。
任务是通过这些交换操作，计算队伍中最小的干扰数。
题目不难，n为奇偶写法一样，找清楚下标就行了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll t;cin>>t;
while(t--){
ll n;cin>>n;
vector<ll> a(n+1,0);
for(ll i=1;i<=n;i++)cin>>a[i];
//ai-1 ai an-i+1,an-i+2
//ai-1 an-i+1 ai an-i+2
for(ll i=2;i<=n/2;i++){
if(a[i]==a[i-1]||a[n-i+1]==a[n-i+2]){
swap(a[i],a[n-i+1]);
}else if(a[i]==a[i-1]&&a[n-i+1]==a[n-i+2]){
swap(a[i],a[n-i+1]);
}
}
ll sum=0;
for(ll i=2;i<=n;i++){
if(a[i]==a[i-1])sum++;
}
cout<<sum<<'\n';
}
return 0;
}D. Kousuke's Assignment
题意翻译
给出一个长度为 n 的数列 ai，要求计算数组中不重叠的子段数量，使得每个子段是美丽的。
一个子段 [l,r] 被认为是美丽的，当且仅当 al+al+1+⋯+ar=0。
你的任务是计算最多有多少个不重叠的美丽子段。
两种思路，离散化映射，set。
最好自己模拟一下过程就知道了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll t; cin >> t;
set<ll> s;
while(t--){
s.clear();
s.insert(0); // 初始前缀和为0
ll ans = 0, sum = 0;
ll n; cin >> n;
vector<ll> a(n+1);
for(ll i = 1; i <= n; i++){
cin >> a[i];
sum += a[i]; // 更新前缀和
if(s.count(sum)){
ans++; // 找到一个美丽子段
s.clear(); // 清空集合，确保子段不重叠
s.insert(0); // 重新初始化前缀和
sum = 0; // 重置前缀和
}
else {
s.insert(sum); // 记录当前前缀和
}
}
cout << ans << endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
vector<long long> a(n);
for(auto &x: a) cin >> x;
// 计算前缀和
vector<long long> prefix_sum(n+1, 0);
for(int i=0; i<n; ++i){
prefix_sum[i+1] = prefix_sum[i] + a[i];
}
// 离散化前缀和
vector<long long> sorted_prefix = prefix_sum;
sort(sorted_prefix.begin(), sorted_prefix.end());
sorted_prefix.erase(unique(sorted_prefix.begin(), sorted_prefix.end()), sorted_prefix.end());
// 映射前缀和到唯一ID
auto get_id = [&](long long x) -> int {
return lower_bound(sorted_prefix.begin(), sorted_prefix.end(), x) - sorted_prefix.begin();
};
int m = sorted_prefix.size();
// 初始化last_occurrence数组为-1
vector<int> last_occurrence(m, -1);
// 初始前缀和0的位置为0
last_occurrence[get_id(0)] = 0;
int count = 0;
int last_end = 0;
for(int i=1; i<=n; ++i){
int id = get_id(prefix_sum[i]);
if(last_occurrence[id] >= last_end){
count++;
last_end = i;
}
last_occurrence[id] = i;
}
cout << count << "\n";
}
}
E. Sakurako, Kosuke, and the Permutation
题意翻译：
Sakurako 的考试结束了，她表现出色，作为奖励，她得到了一个排列 p。Kosuke 因为考试没通过，没收到礼物，因此决定偷偷进入 Sakurako 的房间，把她的排列变得简单。
一个排列 p 被称为简单的，如果对于每个 i（1≤i≤n），满足以下条件之一：
- pi=i
- ppi=i
例如，排列 [1,2,3,4],[5,2,4,3,1] 和 [2,1] 是简单的，而[2,3,1] 和[5,2,1,4,3] 不是。
在每次操作中，Kosuke 可以选择一对 i,j (1≤i,j≤n)并交换pi 和 pj 的位置。
你的任务是计算 Kosuke 最少需要进行多少次操作，才能将排列变成简单的。
题目解析：
典型的交换环问题，我们将 pi=i称为长度为 1的环，将 ppi=i 称为长度为 2的环，将 ppi=i 称为长度为 3的环，以此类推。如果交换两个不同环中的元素，会将它们合并为更大的环。因此，只有在每个环的内部进行交换，才能减少环的长度。
要使得所有元素满足：
- pi=i
- ppi=i
我们可以举以下一个例子来探索规律：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll t;cin>>t;
while(t--){
ll n;cin>>n;
ll ans=0;
vector<ll> a(n+1);
map<ll,ll>mp;
for(ll i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]=i;
}
for(ll i=1;i<=n;i++){
if(a[i]!=i){
if(a[a[i]]!=i){
ll s=mp[i];
ll t=a[i];
swap(a[s],a[t]);
mp[a[s]]=s;
mp[a[t]]=t;
ans++;
}
}
}
cout<<ans<<endl;
}
return 0;
}用并查集统计环的大小。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using namespace std;
const int N=1e6+5;
int n;
int a[N];
int fa[N],siz[N];
bool v[N];
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
x=find(x),y=find(y);
if(x!=y) siz[x]+=siz[y],fa[y]=x;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1,v[i]=0;
for(int i=1;i<=n;i++) merge(i,a[i]);
int ans=0;
for(int i=1;i<=n;i++)
{
int x=find(i);
if(!v[x]) ans+=(siz[x]-1)/2;
v[x]=1;
}
cout<<ans<<'\n';
}
int main ()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}F. Kosuke's Sloth
题意翻译
斐波那契数列定义如下：
- f(1)=f(2)=1
- f(n)=f(n−1)+f(n−2)（n≥3）。
定义 G(n,k)为第 n 个能被 k 整除的斐波那契数的下标。给定 n 和 k，计算 G(n,k)。
由于这个数可能非常大，结果需要对109+7 取模。
例如：G(3,2)=9，因为第 3 个能被 2 整除的斐波那契数是 34，即 [1,1,2,3,5,8,13,21,34]。
emmmm，这个题不可以暴力不用想就超时，但是可以暴力枚举发现规律，下面是暴力枚举代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e9+7;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
vector<ll> a(100000001);
a[0]=1,a[1]=1;
for(ll i=2;i<=100000000;i++){//再多一个0就不可以正常输出了
a[i]=a[i-1]+a[i-2];
}
//for(ll i=0;i<30;i++)cout<<a[i]<<" ";
//cout<<endl;
ll t;cin>>t;
while(t--){
ll n,k;cin>>n>>k;
ll count=0;
for(ll i=1;i<10001;i++){
if(count==n){
cout<<(i-1)%N<<'\n';
break;
}else{
if(a[i]%k==0)count++;
}
}
}
return 0;
}
观察这些下标的规律，对于能除于2能除尽的数以3为公差 ，换个数再试验一下，看看究竟什么规律。
对于能除于3能除尽的数以4为公差.
哦呦， 对于能除于4能除尽的数以6为公差,这个时候就要在尝试别的数据了。
对于能除于5能除尽的数以5为公差。
emmmm异彩纷呈。。 前面都是12为公差，从95开始就不对劲了。。。
所以我们发现不可以直接提交，如果直接提交必WA。
原因在一个数模 N等于 0 并不能代表其下一位一定模 N 后为 1，不符合最小周期的定义。
于是我们发现这个周期一定是最小周期的某个约数，斐波那契数列取模 k 具有周期性，这个周期叫做皮萨诺周期，并且周期 L≤6k。
核心是寻找皮萨诺周期。皮萨诺周期是指斐波那契数列对某个数取模后所形成的周期。例如，对于 k=2，斐波那契数列对 2 取模后的周期是 3，因为 [1, 1, 2, 3, 5, 8, 13, 21, ...] 对 2 取模结果是 [1, 1, 0, 1, 1, 0, 1, 1, ...]。
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
{
ll n,k;
cin>>n>>k;
n%=mod;
if(k==1)
{
cout<<n<<'\n';
continue;
}
int f1=1,f2=1,f3=1;
/*
f1 和 f2 分别表示斐波那契数列中的前两项。
f3 是当前斐波那契数列项的值。
使用 f1 和 f2 生成斐波那契数列，直到找到第一个能够被 k 整除的项（即 f3 == 0）。
每生成一个新项，就增加 cnt，表示到目前为止生成的斐波那契数的个数。
*/
ll cnt=2;
while(f3!=0)
{
f3=(f1+f2)%k;
f1=f2;
f2=f3;
cnt++;
}
cout<<cnt*n%mod<<'\n';
}
return 0;
}G. Sakurako and Chefir
题意翻译
给定一个 n 个节点的树，q 次询问，给定 u,k对于每次询问，你需要操作节点 u 顺着边进行移动操作，满足：
- 最多向树根（深度减小）方向移动 k 次；
- 向叶子（深度增加）方向移动任意次。
问操作结束后与原点 u 的距离最大值。多组询问。
先放个答案代码，以后见。
#include<bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define reg register
#define For(i,l,r) for(reg int i=l;i<=r;++i)
#define FOR(i,r,l) for(reg int i=r;i>=l;--i)
using namespace std;
const int N = 2e5 + 10;
struct Node {
int v, nx;
} e[N << 1];
int T, n, q, tot, idx, h[N], siz[N], son[N], dep[N], fa[N], top[N], dfn[N], id[N], st[N][24], w[N], maxdep, Dep[N];
void add(int u, int v) {
e[++tot] = (Node){v, h[u]};
h[u] = tot;
}
void clear_st() {
For(i,1,n) {
For(j,0,23) st[i][j] = 0;
}
}
void clear() {
tot = idx = maxdep = 0;
For(i,1,n) {
h[i] = siz[i] = son[i] = dep[i] = fa[i] = top[i] = dfn[i] = id[i] = w[i] = Dep[i] = 0;
}
clear_st();
}
void dfs(int x, int f) {
fa[x] = f;
dep[x] = dep[f] + 1;
maxdep = max(maxdep, dep[x]);
siz[x] = 1;
int maxi = 0;
for (int i = h[x]; i; i = e[i].nx) {
int y = e[i].v;
if(y == f) continue;
dfs(y, x);
Dep[x] = max(Dep[x], Dep[y] + 1);
siz[x] += siz[y];
if(maxi < siz[y]) {
maxi = siz[y];
son[x] = y;
}
}
}
void dfs1(int x, int tp) {
top[x] = tp;
dfn[x] = ++idx;
id[idx] = x;
if(son[x]) dfs1(son[x], tp);
for (int i = h[x]; i; i = e[i].nx) {
int y = e[i].v;
if(y == fa[x] || y == son[x]) continue;
dfs1(y, y);
}
}
int ask(int l, int r) {
if(l > r || r > n || l < 1) return 0;
int k = __lg(r-l+1);
return max(st[l][k], st[r-(1<<k)+1][k]);
}
void dfs2(int u) {
for (int i = h[u]; i; i = e[i].nx) {
int v = e[i].v;
if(v == fa[u]) continue;
if(fa[v]) {
w[v] = max(0ll, max(ask(dfn[u]+1, dfn[v]-1), ask(dfn[v]+siz[v], dfn[u]+siz[u]-1)) - dep[u]) + maxdep - dep[u] + 1;
}
dfs2(v);
}
}
int jp(int u, int k) {
int ans = Dep[u];
int x = u;
k--;
if(k == -1 || u == 1) return Dep[u];
while(1) {
if(k > (dfn[x] - dfn[top[x]])) {
k -= (dfn[x] - dfn[top[x]] + 1);
ans = max(ans, ask(dfn[top[x]], dfn[x]) - (maxdep - dep[u] + 1));
x = fa[top[x]];
} else {
ans = max(ans, ask(dfn[x] - k, dfn[x]) - (maxdep - dep[u] + 1));
break;
}
}
return ans;
}
void solve() {
cin >> n;
clear();
For(i,1,n-1) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1, 0);
dfs1(1, 1);
For(i,1,n) st[i][0] = dep[id[i]];
for (reg int j = 1; (1 << j) <= n; ++j) {
for(reg int i = 1; i + (1 << j) - 1 <= n; ++i) {
st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
}
dfs2(1);
For(i,1,n) st[i][0] = w[id[i]];
for (reg int j = 1; (1 << j) <= n; ++j) {
for(reg int i = 1; i + (1 << j) - 1 <= n; ++i) {
st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
}
cin >> q;
while(q--) {
int u, k;
cin >> u >> k;
k = min(k, dep[u] - 1);
cout << jp(u, k) << ' ';
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T;
while(T--) solve();
return 0;
}Good night！