SDNU_ACM_ICPC_2021_Winter_Practice_2nd [个人赛]
A - Different Divisors
题意：
输入一个数x，让你找到一个至少有四个因子且这四个因子的大小差至少为x的一个最小的数
思路：
首先我们假设要求的这个数是ans，要让她最小，则其中四个因子的两个就是1和ans本身，这样我们只需要找到剩下的两个因子a，b；使得1，a，b三个数直接的大小差至少为x即可。但是，如果你找的a和b是一个合数，那这个合数至少有一个小于本身且不同于1和它本身的一个因子，这个因子也一定是ans的因子，这样的话就不能让1和这个因子的大小差不小于x了，所以说我们必须要找素数。
第一步先打个素数表，然后再进行一次循环，找两个满足条件的数就break掉
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
ll tr[100005];
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
bool is_prime(ll n)///素数判定，用来打表的
{
if(n == 1) return 1;
for(int i = 2; 1ll * i * i <= n; ++i)
{
if(n % i == 0) return 0;
}
return 1;
}
int main()
{
ll len = 0;
for(int i = 1; i <= 100005; i++)//打表
{
if(is_prime(i) == 1)
tr[len++] = i;
}
ll n, t;
//cout<<tr[0];
t = IntRead();
while(t--)
{
n = IntRead();
ll a = 1, ans = 1, sum = 0;//a是指上一个的因子，ans是我们最终的结果，sum用来计数
for(int i = 1; i < 100005; i++)
{
if(tr[i] - a >= n)
{
ans *= tr[i];//如果找到了就乘起来
a = tr[i];//更新a的值
sum++;//用来计数
}
if(sum == 2)//满两个数就退出循环
{
cout<<ans<<endl;
break;
}
}
}
return 0;
}
D - 这不是签到题
题意：
原来你有两个二进制数a和b，而d是这两个二进制数按位相加，不会进位的加法，每个位最大是2，数字大的就是大，比如102 > 21 021 = 21,还有的是这个d数字不喜欢重复的东西，所以会把自身连续的重复的数字变成不重复的，比如：1211 —> 121 , 022000 —> 020。不幸的是，Mike把a弄丢了，为了让他开心，你必须找到一个a，使得d的值最大
思路：
因为是找最大的数，我们肯定是让每一位都尽可能的大，但是还得考虑不能出现重复的，因为一旦出现重复的数，你的位数就会少，肯定就会小，举个栗子：
b是001011，要让d最大，那么a的第一位绝对是1，这个时候d的第一位是1；要防止d串去重，我们只能让a的第二位是0，所以d的第二位是0；下一个就可以不管b是几，直接让a取最大，也就是a的第三位是1，这个时候d的第三位是1+1也就是2；因为第三位是2，我们要避免第四位也是2而被去重了，所以就要看b串的第四位是0，我们就让a的第四位是1，所以d的第四位是1……就这样一直判断下去
脱离这个例子，我们会发现d的第i位是由d的第i-1位和b的第i位这两个数来决定的，所以可以分情况讨论一下：
当d的第i-1位是2的时候，如果bi是0，则ai取1，如果bi是1，则ai取0。
当d的i-1位是1的时候，如果bi是0，则ai取0,；如果bi是1，则ai取1
当d的第i-1位是0的时候，就可以不用管bi的值，直接让ai取1。
记得每次都要更新ai，bi，di的值
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
int main()
{
int t, n, a, b,c;
string s;
t = IntRead();
while(t--)
{
n = IntRead();
cin>>s;
c = 1;
b = s[0] - '0';
a = (s[0] - '0') + c;
printf("%d",c);
//cout<<a<<' '<<b<<' '<<c<<endl;
for(int i = 1; i < s.size(); i++)
{
b = s[i] - '0';
if(a == 1)
{
if(b == 0)
{
c = 0;
printf("0");
}
else
{
c = 1;
printf("1");
//cout<<1;
}
}
else if(a == 2)
{
if(b == 1)
{
c = 0;
printf("0");
///cout<<c;
}
else
{
c = 1;
printf("1");
//cout<<c;
}
}
else if(a == 0)
{
c = 1;
printf("1");
//cout<<c;
}
a = b + c;
//cout<<a<<' '<<b<<' '<<c<<endl;
}
cout<<endl;
}
return 0;
}
G - A Simple Problem with Integers
线段树区间修改加区间查询的板子题
本来抱着wa的心态把之前wa了的板子打上去了，只不过这次把所有的int全换成了ll，结果AC了，可给我高兴坏了.jpg
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
//#define endl '/n'
//#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-') w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
ll tr[100005], d[400005], b[400050];
ll n, a, f, c, k, q;
void built(ll s, ll t, ll p)
{
if(s == t)
{
d[p] = tr[s];
return;
}
ll m = (s + t) / 2;
built(s, m, p * 2);
built(m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
void update2(ll l, ll r, ll c, ll s, ll t, ll p)
{
if(l <= s && t <= r)
{
d[p] += c * (t - s + 1);
b[p] += c;
return;
}
ll m = (s + t) / 2;
if(b[p])
{
d[p * 2] += b[p] * (m - s + 1);
d[p * 2 + 1] += b[p] * (t - m);
b[p * 2] += b[p];
b[p * 2 + 1] += b[p];
b[p] = 0;
}
if(l <= m)
update2(l, r, c, s, m, p * 2);
if(r > m)
update2(l, r, c, m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
ll getsum2(ll l, ll r, ll s, ll t, ll p)
{
if(l <= s && t <= r)
{
return d[p];
}
ll m = (s + t) / 2;
if(b[p])
{
d[p * 2] += b[p] * (m - s + 1);
d[p * 2 + 1] += b[p] * (t - m);
b[p * 2] += b[p];
b[p * 2 + 1] += b[p];
b[p] = 0;
}
ll sum = 0;
if(l <= m)
sum += getsum2(l, r, s, m, p * 2);
if(r > m)
sum += getsum2(l, r, m + 1, t, p * 2 + 1);
return sum;
}
int main()
{
char a;
n = IntRead();
q = IntRead();
for(int i = 1; i <= n; i++)
tr[i] = IntRead();
built(1, n, 1);
while(q--)
{
cin>>a;
if(a == 'Q')
{
f = IntRead();
c = IntRead();
cout<<getsum2(f, c, 1, n, 1)<<'\n';
}
else
{
f = IntRead(), c = IntRead(), k = IntRead();
update2(f, c, k, 1, n, 1);
// for(int i = 1; i <= 10; i++)
// cout<<d[i]<<' ';
}
}
return 0;
}
H - 最少拦截系统
题意：
导弹拦截系统发射的炮弹第一次可以到达任意高度，该系统之后所能达到的高度不会高于上次拦截的高度，问你需要几套系统能完全拦截导弹
思路：
当时我一看这个题，就寻思这不是那动态规划嘛，之前比较懒没学，就直接跳过了，做到后面发现这是动态规划吗，怎么做出来十几个人，就感觉不对劲，就不抱希望地回头仔细读题，却发现可以直接贪心做
我是先取了一个数组d，用来存需要的拦截系统，最坏的情况下是一个炮弹比一个高，所以数组得开三万，初始只有一个系统，其值为第一个炮弹的高度，两个for循环，外循环是对炮弹的高度 tr[i] ，内循环是对出现的系统的高度d[j]，如果tr[i] > 所有的d[j]，说明前面的所有系统都不好使了，需要一个新系统，这个新系统的d[len++] = tr[i]；如果tr[i] < 某一个的d[j]，说明第j个系统能拦住他，就可以更新一下这个d[j] 的值为tr[i]。最后只需要输出数组的长度即可
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
int tr[30005], d[30005];
int main()
{
int n;
while(cin>>n)
{
for(int i = 1; i <= n; i++)
tr[i] = IntRead();
d[1] = tr[1];
int len = 1, k = 0;//数组长度为len，初始为1，k用来判断是否需要新系统
for(int i = 2; i <= n; i++)
{
k = 0;//每次循环都要初始化k的值
for(int j = 1; j <= len; j++)
{
if(tr[i] <= d[j])
{
d[j] = tr[i];
k = 1;
break;//找到了就跳出，进行下一个炮弹的拦截
}
}
if(k == 0)//k == 0说明没找到能拦截的系统，就得添加新系统
{
d[++len] = tr[i];
}
}
cout<<len<<endl;
}
return 0;
}
I - How Many Tables
并查集板子题，但是记得要初始化数组，一不小心就wa了.jpg
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
int tr[10005];
int find1(int x)
{
if(tr[x] == x)
return x;
if(tr[x] != x)
{
tr[x] = find1(tr[x]);
return tr[x];
}
}
void ran(int a, int b)
{
int x = find1(a);
int y = find1(b);
if(x != y)
tr[y] = x;
}
int main()
{
int n, m, a, b, t;
t = IntRead();
while(t--)
{
int sum = 0;
memset(tr, 0, sizeof(tr));
n = IntRead();
m = IntRead();
for(int i = 1; i <= n ; i++)
{
tr[i] = i;
}
for(int i = 1; i <= m; i++)
{
a = IntRead();
b = IntRead();
ran(a, b);
}
for(int i = 1; i <= n; i++)
{
if(tr[i] == i)
sum++;
}
printf("%d\n",sum);
//cout<<sum<<endl;
}
return 0;
}
M - Intersecting Lines
题意：
给你四个点，（x1,y1）（x2,y2）（x3,y3）（x4,y4），前两个点构成一条直线，后两个点构成一条直线，问你这两条直线 位置关系
思路：
看起来挺简单的，其实你得对解析几何了解的比较透彻才行
我用的是最老土的办法：设直线，推公式，而非那些花里胡哨的向量计算法（好吧，其实是我忘了向量那些公式是什么了……手动狗头
相信学过高中数学的同志们都知道考试最后一个解析几何的题，基本上都要考虑斜率不存在的特殊情况！
对，这个题你得先考虑斜率不存在的时候，两个直线的斜率都不存在的时候，你还得判断这两条直线是不是同一条直线（我就是wa在了这里！！！当时想了半天都觉得自己思路没问题，后来就下定决心如果再找不出错就去吃饭，结果一不小心找到了.jpg），判断完斜率不存在之后就可以直接算k1,b1,k2,b2，然后推个公式带进去即可。还要注意题目对输出的一些要求就能AC。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
int main()
{
int n;
double x1, x2, x3, x4, y1, y2, y3, y4;
scanf("%d",&n);
printf("INTERSECTING LINES OUTPUT\n");
while(n--)
{
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
if(x1 == x2 && x3 == x4)//同时没有斜率
{
if(x1 == x3)//判断是不是重合了
cout<<"LINE"<<endl;
else
cout<<"NONE"<<endl;
}
else if(x1 == x2 && x3 != x4)//一个有斜率一个没有斜率
{
double k2,b2,x,y;
k2 = (y4 - y3) / (x4 - x3);//公式，手推
b2 = (x4 * y3 - x3 * y4) / (x4 - x3);
x = x1;
y = k2 * x + b2;
printf("POINT ");
printf("%.2lf %.2lf\n", x, y);
// cout<<x<<' '<<y<<endl;
}
else if(x1 != x2 && x3 == x4)//同样是一个有斜率一个没有
{
double k1,b1,x,y;
k1 = (y2 - y1) / (x2 - x1);
b1 = (x2 * y1 - x1 * y2) / (x2 - x1);
x = x3;
y = k1 * x + b1;
printf("POINT ");
printf("%.2lf %.2lf\n", x, y);
//cout<<x<<' '<<y<<endl;
}
else
{
double k1, k2, b1, b2, x, y;
k1 = (y2 - y1) / (x2 - x1);
k2 = (y4 - y3) / (x4 - x3);
b1 = (x2 * y1 - x1 * y2) / (x2 - x1);
b2 = (x4 * y3 - x3 * y4) / (x4 - x3);
if(k1 == k2)//斜率相同则进行进一步的判断
{
if(b1 == b2)//重合
printf("LINE\n");
else if(b1 != b2)
printf("NONE\n");
}
else
{
x = (b2 - b1) / (k1 - k2);
y = k1 * x + b1;
printf("POINT ");
printf("%.2lf %.2lf\n",x, y);
}
}
}
printf("END OF OUTPUT\n");
return 0;
}
J - The Suspects
题意：
0号同学有带病毒的嫌疑，给你n个团体，如果团体内有一个人有嫌疑，则整个团体都有嫌疑，问有多少带病毒嫌疑的人
思路：
并查集的变形，因为0号有嫌疑，最后要求所有带病毒嫌疑的人，就可以利用并查集合并并查找0号个体所在的团体，最终输出该团体的人数即可。
又因为是0号有嫌疑，是最小的一号，我们就可以采用取小原则，而非之前的靠左原则，即合并的时候谁的号小就归顺谁，这样能保证头领是0号，然后查找的时候只需要找他的头领是不是0号即可！
#include <bits/stdc++.h>
using namespace std;
const int N = 30000 + 5;
int n, m, k, tr[N];//
void init()//初始化数组
{
for(int i = 0; i < n; ++i)
{
tr[i] = i;
}
}
int find1(int v)//俗称找爹函数
{
if(f[v] == v)//找到了就返回爹
return v;
else//没找到就继续找爹
{
f[v] = find1(f[v]);
return f[v];
}
}
void ranran(int u, int v)//合并
{
int x = find1(u);//先把x，y的爹找出来
int y = find1(v);
if(x < y)//取小原则
f[y] = x;
else if(x > y)
f[x] = y;
}
int a, b, c, sum;//sum用来计数，记得要清0
int main()
{
while(cin>>n>>m)
{
if(n == 0 && m == 0)//输入都是0的时候结束程序
break;
init();//初始化
sum = 0;//清0
while(m--)//m组例子
{
cin>>a>>b;
a--;//a个数,而b就是a个数中的一个，所以写while之前得让a--
while(a--)
{
cin>>c;
ranran(b, c);//每一次都A1与Ai进行并查集操作
}
}
for(int i = 0; i < n; i++)
{
if(f[i] == 0 || find1(i) == 0)//两种情况，一种是本身就是0，另一种是认的爹是0
sum++;
}
cout<<sum<<endl;
}
return 0;
}
B - String LCM
题意：
给你n对字符串，让你判断两个串的“最小公倍数”，如：abab 与 ab的最小公倍数是abab，如果没有的话就输出-1
代码如下，具体思路我会单独开一个博客写
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
int next1[100005],next2[100005], len1, len2;
string s1, s2;
void getnext1()
{
int j, k;
j = 0;
k = -1;
next1[0] = -1;
while(j < len1)
{
if(k == -1 || s1[j] == s1[k])
next1[++j] = ++k;
else
k = next1[k];
}
}
void getnext2()
{
int j, k;
j = 0;
k = -1;
next2[0] = -1;
while(j < len2)
{
if(k == -1 || s2[j] == s2[k])
next2[++j] = ++k;
else
k = next2[k];
}
}
int gcd(int a, int b)
{
if(b) return gcd(b, a % b);
else return a;
}
int main()
{
int n, a, b, k;
// string s1, s2;
cin>>n;
while(n--)
{
memset(next1, 0, sizeof(next1));
memset(next2, 0, sizeof(next2));
k = 1;
cin>>s1>>s2;
len1 = s1.size();
len2 = s2.size();
getnext1();
getnext2();
a = len1 - next1[len1];
b = len2 - next2[len2];
if(len1 % a != 0)
a = len1;
if(len2 % b != 0)
b = len2;
// for(int i = 1; i <= len1; i++)
// cout<<next1[i]<<' ';
// cout<<len1 - next1[len1 - 1]<<endl<<len2 - next2[len2 - 1];
if(a != b || len1 % a != 0 || len2 % b != 0)
{
// cout<<a<<' '<<b<<endl<<len1<<' '<<len2;
// cout<<"第一处"<<endl;
cout<<-1;
}
else
{
for(int i = 0; i < a; i++)
{
if(s1[i] != s2[i])
{
k = 0;
break;
}
}
if(k == 0)
{
cout<<-1;
}
else
{
int c = (len1 / a * len2 / b) / gcd(len1 / a, len2 / b);
while(c--)
{
for(int i = 0; i < a; i++)
cout<<s1[i];
}
}
}
cout<<endl;
}
return 0;
}
}
总结：
A题：思维题，最少四个因子，代表你只需要找两个因子即可，再仔细分析一下就知道是找素数因子
B题: KMP的next数组的思维题（我是真没想到是KMP的题.jpg
D题：01字符串的问题，题干很长，看似很难，其实不难，就是第一位一定是1，然后下面每一位都判断选1的时候加起来和上一位一不一样，不一样就选1，一样就选0
G题：线段树区间查询区间修改，套板子即可
H题：贪心，每次从第一个系统开始判断，如果能拦住就更新一下，拦不住就再找一个系统，最后输出总系统的个数
I题：并查集板子
J题：并查集的升级版，根据题意改一下find函数，将以左为尊改为以小为尊
M题：给你四个点，前两个点确定一条直线，后两个点确定一条直线，问你这两条直线的位置关系，题目不难，就是细节比较多，判斜率不存在和斜率存在，在分别判是平行还是重合还是相交，特别注意不要忘了判两个直线都没斜率的时候是否重合，剩下的的就考的是数学知识，推个公式即可