又是一天

---

A - On and Off

判断是否是同一天。

#include<bits/stdc++.h>
#include<vector>
#define ll long long
using namespace std;
const int maxn = 2e5 + 10;int main() {int s, t, x;cin >> s >> t >> x;if(s < t){ // 同一天 if(s<=x && x<t) cout <<"Yes";else cout << "No";}else{//不同 if(x<t || s<=x) cout << "Yes";else cout << "No";}return 0;
}

B - Takahashi’s Secret

思路：从第x个人开始找，遇到之前出现过的人的时候结束。
dfs

#include<bits/stdc++.h>
#include<vector>
#define ll long long
using namespace std;
const int maxn = 1e6+10;int a[maxn];
bool v[maxn];
int dfs(int x, int cnt){if(v[a[x]] == 1){return cnt;}v[a[x]] = 1;return dfs(a[x],cnt+1);
}
int main(){int n, x;cin >> n >> x;for(int i=1; i<=n; i++) cin >> a[i];v[x] = 1;cout << dfs(x, 1) << endl;return 0;
}

循环

#include<bits/stdc++.h>
#include<vector>
#define ll long long
using namespace std;
const int maxn = 2e5 + 10;int vis[maxn];
int a[maxn];
int main() {int n, x;cin >> n >> x;for(int i=1; i<=n; i++) cin >> a[i];int res = 0;while(vis[x] == 0){vis[x] = 1;x = a[x];res++;} cout << res << endl;return 0;
}

C - Final Day

题意：问每个人经历第四次考试之后能否成为第k名。
思路：将前三次成绩排序，取第i个人第四次最高分其余人都0分，如果能大于第k个人的成绩的话就是满足条件的。

#include<bits/stdc++.h>
#include<map>
#define ll long lnog
using namespace std;
const int maxn = 1e6 + 10;
int a[maxn], b[maxn];
bool cmp(int a, int b){return a > b;
}
int main() {int n, k;cin >> n >> k;for(int i=1; i<=n; i++){int x, y, z;cin >> x >> y >> z;a[i] = x+y+z;b[i] = a[i];}sort(b+1, b+n+1, cmp);for(int i=1; i<=n; i++){if(a[i] + 300 >= b[k]){cout << "Yes\n";}else{cout << "No\n";}}return 0;
}

D - Linear Probing

题意：有一个长度为$2^{20}$的数组，初始为$-1$，查询Q次，每次有两种操作：

1. $t=1，x$，从位置x(%len)开始往后找到第一个值为$-1$的位置，将其修改为$-1$。
   ·最后一个位置的后面是第一位。
2. $t=2，x$，输出第x个位置的数。

思路：对于每一个被修改为-1的位置在之后的查询中都可以忽略掉，所以我们可以每修改一个点就把它和它后面的点合并，减少查询次数。这里使用并查集将其合并。

#include<bits/stdc++.h>
#include<map>
#define ll long long
using namespace std;
const int maxn = (1<<20);
ll a[maxn+10];
int fa[maxn+10];
int find(int x){if(x == fa[x]) return x;return fa[x] = find(fa[x]);
}
void join(int x, int y){ll fx = find(x);ll fy = find(y);if(fx != fy){fa[x] = fy;}
}
int main() {for(int i=0; i<=maxn; i++) {fa[i] = i; //初始化父节点a[i] = -1; }int q;cin >> q;while(q--){ll p, x;cin >> p >> x;if(p == 1){int ind = find(x%maxn); // 如果没有被修改过就是本身a[ind] = x; join(ind, (ind+1)%maxn); // 将其与后面的点合并}else{cout << a[x%maxn] << endl;}}return 0;
}

E - Integer Sequence Fair

题意：求$m^{k^n}，1\le N,K,M\le 10^{18}$
思路：由于$k^n$很大，所以这里要用欧拉降幂来处理。
这里给出欧拉降幂的公式，证明有兴趣可以自学。

其中$\varphi (p)$表示p的欧拉函数值。
欧拉函数：$\varphi (n):[1,n]中与n互质的数的个数$。

所以$m^{k^n}=m^{k^{n}mod\varphi (p)}$，p是质数，所以$\varphi (p)=p-1$。
即：$m^{k^n}=m^{k^{n}mod(p-1)}$，然后就可以通过两次快速幂求出。

#include<bits/stdc++.h>
#include<map>
#define ll long long
using namespace std;
const ll mod = 998244353;
ll qpow(ll a, ll b, ll mod){a %= mod;ll res = 1;while(b){if(b&1) res = res * a % mod;b >>= 1;a = a * a % mod;}return res;
}// O(根号n) 单次求欧拉函数
int qphi(int a){int res = a;for(int i=2; i<=a/i; i++){if(a % i == 0){res = res / i * (i - 1);while(a%i == 0) a /= i;}}if(a > 1) res = res / a * (a - 1);return res;
}
int main() {ll n, k, m;cin >> n >> k >> m;if(m % mod == 0) cout << 0 << endl;else {ll tmp = qpow(k, n, mod-1);ll res = qpow(m, tmp, mod);cout << res << endl;}return 0;
}