A.信息传递
题目描述：
有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为i的同学的信息传递对象是编号为Ti的同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？
输入格式
输入共2行。
第1行包含1个正整数n表示n个人。
第2行包含n个用空格隔开的正整数(T1，T2...Tn)，其中第i个整数Ti表示编号为i的同学的信息传递对象是编号为Ti的同学， 且(Ti leq) n$ 且 (Ti
eq i)，数据保证游戏一定会结束。
输出格式
输出共 1 行，包含 1 个整数，表示游戏一共可以进行多少轮。
样例
(input)
5
2 4 2 3 1
3
思路
很简单的一道并查集的题目，直接上代码，话不多说，脚写都没问题。。。
代码实现
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 200010;
int fa[maxn], m[maxn], n, last;
int minans = 0x3f3f3f3f;
int a;
int find_root(int x) {
if (fa[x] != x) {
int last = fa[x];
fa[x] = find_root(fa[x]);
m[x] += m[last];
}
return fa[x];
}
void find(int a, int b) {
int x = find_root(a), y = find_root(b);
if (x != y) {
fa[x] = y;
m[a] = m[b] + 1;
} else
minans = min(minans, m[a] + m[b] + 1);
return;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a);
find(i, a);
}
printf("%d
", minans);
return 0;
}
B.传染病控制
题目描述
近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府 决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国 的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO （世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究消除，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控 制办法。
研究表明，这种传染病的传播具有两种很特殊的性质；
第一是它的 传播途径是树型的，一个人(X)只可能被某个特定的人(Y)感染，只要(Y)不得病，或者是(X,Y)之间的传播途径被切断，则(X)就不会得病。
第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。
这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手 不够，同时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与 当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传 播途径的顺序，以使尽量少的人被感染。
你的程序要针对给定的树，找出合适的切断顺序。
输入格式
输入格式的第一行是两个整数(n(0 leq n leq 100))和(p)。
接下来p行，每一行有两个整数i和j，表示节点i和j间有边相连（意即，第i人和第j人之间有传播途径相连,可相互感染）。其中节点1是已经被感染的患者。
样例
(input)
7 6
1 2
1 3
2 4
2 5
3 6
3 7
(output)
3
思路
大致实现都写在了注释里面，不多写了
代码实现
#include <bits/stdc++.h>
const int maxn = 300 + 5, Inf = 2147483647;
int n, m, max_dis, ans = 2147483647;
int dis[maxn], head[maxn], Cut[maxn], f[maxn], deep[maxn][maxn], cnt[maxn];
struct Edge {
int next, to;
} e[maxn << 1];
void Insert(int u, int v) {
e[++head[0]].to = v;
e[head[0]].next = head[u];
head[u] = head[0];
}
void dfs(int now, int fa) {
for (int i = head[now]; i; i = e[i].next) {
int v = e[i].to;
if (v == fa)
continue;
dis[v] = dis[now] + 1;
f[v] = now;
max_dis = std::max(max_dis, dis[v]);
dfs(v, now);
}
}
void tag(int u, int color) { //把以u为根的子树都打上隔断标记
Cut[u] = color;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (v == f[u])
continue;
Cut[v] = color;
tag(v, color);
}
}
int calc(int dep) { //计算dep层感染人数
int sum = 0;
for (int i = 1; i <= cnt[dep]; i++)
if (Cut[deep[dep][i]] == 0)
sum++;
return sum;
}
void Search(int dep, int sum) { // sum到dep层时已感染的人数
if (sum >= ans)
return;
if (dep > max_dis || calc(dep) == 0) { //当前层无感染或超过了最大深度
ans = std::min(ans, sum);
return;
}
for (int i = 1; i <= cnt[dep]; i++) { //枚举dep层的每一个点
int to = deep[dep][i];
if (Cut[to] == 1)
continue; // Cut[i]==1表示i已经被隔断，不会被传染
tag(to, 1); //隔断to和to的子树
Search(dep + 1, sum + calc(dep)); //爆搜下一层
tag(to, 0); //取消对to和to子树的隔断标记
}
}
void Solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
Insert(u, v);
Insert(v, u);
}
dfs(1, 0); //预处理出点到根几点的距离和点的父亲节点
for (int i = 1; i <= n; i++) // deep[i][j]:第i层的第j个点
deep[dis[i]][++cnt[dis[i]]] = i; // cnt[i]:第i层的节点个数
Search(1, 1); //逐层爆搜
printf("%d
", ans);
}
int main() {
Solve();
return 0;
}
C.排列
题目描述
给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。
例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。
输入格式
输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0，1，2，3，4，5，6，7，8，9。
输出格式
每个数据仅一行，表示能被d整除的排列的个数。
样例
(input)
7
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29
(output)
1
3
3628800
90
3
6
1398
思路
看数据范围很弱，显然可以用状压dp求解，同时也可以用全排列搞，即暴力枚举出所有情况。
思路1（状压dp）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 15;
int f[1<<maxn][1100];
int a[maxn];
char s[maxn];
int cnt[maxn];
int T,d;
int J[]={0,1,2,6,24,120,720,5040,40320,362880,3628800};//初始化1到10的全排列
int main(){
cin>>T;
while(T--){
memset(cnt,0,sizeof(cnt));
memset(f,0,sizeof(f));
cin>>s>>d;
int len = strlen(s);
for(int i=0;i<len;++i){
a[i+1] = s[i] - '0';
cnt[a[i+1]]++;//预处理数字为a[i+1]的个数
}
f[0][0] = 1;
int lim = (1<<len);
for(int i=0;i<lim;++i){//枚举状态
for(int k=0;k<d;++k){//枚举余数
if(f[i][k])//优化效率，0的时候就不用加了
for(int j=0;j<len;++j){//枚举放第几位
if((i & (1<<j)) == 0){
f[i|(1<<j)][(k*10+a[j+1])%d] += f[i][k];//状态转移
}
}
}
}
int ans = f[lim-1][0];//答案就是状态为全部填入，余数为0的情况数
for(int i=0;i<=9;++i){
if(cnt[i]){
ans /= J[cnt[i]];//答案除以有几个同样数字的全排列，因为数字一样的话不管哪个放在一个位置都是一种
}
}
cout<<ans<<endl;
}
}
思路2（dfs枚举）
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int Maxn = 20;
char s[Maxn];
int d, num[Maxn];
void get_num() {
num[0] = strlen(s);
for (register int i = 1; i <= num[0]; i++) {
num[i] = s[i - 1] - '0';
}
}
ll dfs(int pre, int s, ll tot) {
if (pre == num[0])
return tot % d == 0;
bool vis[Maxn];
for (int i = 0; i <= 10; i++) vis[i] = 0;
ll t = 0;
for (int i = 1; i <= num[0]; i++) {
if (vis[num[i]] || (s & 1 << i - 1))
continue;
vis[num[i]] = 1;
t += dfs(pre + 1, s | 1 << i - 1, tot * 10 + num[i]);
}
return t;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s%d", s, &d);
get_num();
printf("%lld
", dfs(0, 0, 0));
}
}
D.最大数
题目描述
现在请求你维护一个数列，要求提供以下两种操作：
1.查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。
2.插入操作。
语法： A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t = 0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是非负整数并且在长整范围内。
注意：初始时数列是空的，没有一个数。
输入格式
第一行两个整数，M和D，其中M表示操作的个数（M leq 200000），D如上文中所述，满足(0 leq D leq 2000000000)
接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
样例
(input)
5 100
A 96
Q 1
A 97
Q 1
Q 2
(output)
96
93
96
思路
现在看之前集训的题目真的好水啊23333，这不就是个裸裸的线段树吗。。感觉没啥可说的了，直接上代码（逃）
代码实现
#include<bits/stdc++.h>
using namespace std;
int tree[200050 << 2], a[200050], M, D;
int ad, check;
char c;
void modify(int rt, int l, int r, int x, int y){
if(l == r){
tree[rt] += y;
return;
}
int mid = (l + r) >> 1;
if(x <= mid) modify(rt << 1, l, mid, x, y);
else modify(rt << 1 | 1, mid+1, r, x, y);
tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
int query(int rt, int l, int r, int s, int t){
if(s <= l && t >= r){
return tree[rt];
}
int mid = (l + r) >> 1;
if(t <= mid) return query(rt << 1, l, mid, s, t);
else if(s > mid) return query(rt << 1 | 1, mid + 1, r, s, t);
else return max(query(rt << 1, l, mid, s, t), query(rt << 1 | 1, mid+1, r, s, t));
}
void solve(){
int maxans = 0;
int len = 0;
scanf("%d%d", &M, &D);
for(int i = 1; i <= M; i++){
cin>>c;
if(c == 'A'){
scanf("%d", &ad);
modify(1, 1, 200000, ++len, (maxans + ad) % D);
}else{
scanf("%d", &check);
maxans = query(1, 1, 200000, len - check + 1, len);
printf("%d
", maxans);
}
}
}
int main(){
solve();
return 0;
}
之前集训手懒一篇题解都没有写，最近不太想打新题，打算把做过的题目重新写一边题解，尽快补完吧