题目链接

A.Race

题意：
$小红和小明赛跑，速度分别为v1,v2，如果小明在某个整数秒超过小红t米及以上$
$就停下来休息s秒，赛道长总共l米，问谁会赢$
题解：
$l<=10000,并且l是v1,v2的公倍数$
$所以直接模拟每秒，如果他俩距离大于等于t$
$就让小明停止$
$看他俩谁先到终点或者同时到达$
AC代码

/*Author:zzugzxLang:C++Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int v1,v2,t,s,l;cin>>v1>>v2>>t>>s>>l;int sec=1,a=0,b=0,f=0;while(1){if(a-b>=t&&!f)f=s;if(!f)a+=v1;else f--;b+=v2;if(a==l||b==l)break;sec++;}if(a==l&&b==l)cout<<"Tie "<<sec;else if(a==l)cout<<"Ming "<<sec;else cout<<"Hong "<<sec;return 0;
}

---

B.Min Value

题意：
$给n个整数，找出任意两个数使得abs(a_i+a_j)最小$
$在这个前提下使i+j最小$
题解：
$对于每个数相加abs最小的就是他的负数$
$所以直接找每个数的负数及其左右两边数$
$并且提前维护序号，如果值相同尽量找到小的i+j$
AC代码

/*Author:zzugzxLang:C++Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};struct node{int x,id;bool operator <(const node &t)const{return x<t.x;}
}a[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i].x,a[i].id=i;sort(a+1,a+1+n);int ans1=inf,ans2;for(int i=1;i<=n;i++){int p=lower_bound(a+1,a+1+n,(node){-a[i].x,a[i].id})-a;p=max(1,p);if(p>1&&p-1!=i)if(abs(a[i].x+a[p-1].x)<ans1)ans1=abs(a[i].x+a[p-1].x),ans2=a[i].id+a[p-1].id;else if(abs(a[i].x+a[p-1].x)==ans1)ans2=min(ans2,a[i].id+a[p-1].id);if(p!=i)if(abs(a[i].x+a[p].x)<ans1)ans1=abs(a[i].x+a[p].x),ans2=a[i].id+a[p].id;else if(abs(a[i].x+a[p].x)==ans1)ans2=min(ans2,a[i].id+a[p].id);if(p+1<=n&&p+1!=i)if(abs(a[i].x+a[p+1].x)<ans1)ans1=abs(a[i].x+a[p+1].x),ans2=a[i].id+a[p+1].id;else if(abs(a[i].x+a[p+1].x)==ans1)ans2=min(ans2,a[i].id+a[p+1].id);}cout<<ans1<<' '<<ans2;return 0;
}

---

C. Coronavirus

题意：
$n*m的图中有高危路段，用*表示$
$每个以高危路段为中心的九宫格都不能走$
$问从S到E最少需要多少步或者确定不能到达$
题解：
$先对不能走的路进行标记$
$枚举整个图如果遇到星号之间对周围的九宫格进行标记$
$然后直接bfs，队列中维护坐标和步数$
$如果坐标对应的是终点输出步数，否则最后输出不能到达$
AC代码

/*Author:zzugzxLang:C++Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};char g[100][100];
bool vis[100][100];
struct node{int x,y,s;
};
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n,m;cin>>n>>m;int sx,sy;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>g[i][j];if(g[i][j]=='S')sx=i,sy=j;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(g[i][j]=='*'){vis[i][j]=1;for(int k=0;k<8;k++){int dx=i+dir[k][0];int dy=j+dir[k][1];if(dx<1||dx>n||dy<1||dy>m)continue;if(g[dx][dy]=='E'){cout<<"Impossible";return 0;}vis[dx][dy]=1;}}queue<node> q;q.push((node){sx,sy,0});vis[sx][sy]=1;while(!q.empty()){node p=q.front();q.pop();if(g[p.x][p.y]=='E'){cout<<p.s;return 0;}for(int i=0;i<4;i++){int dx=p.x+dir[i][0];int dy=p.y+dir[i][1];if(dx<1||dx>n||dy<1||dy>m||vis[dx][dy])continue;vis[dx][dy]=1;q.push((node){dx,dy,p.s+1});}}cout<<"Impossible";return 0;
}

---

D. Array

题意：
$一个数组全部异或的值为x，全部相加为y$
$问数组最短长度是多少$
题解：
$原题的简化版 codeforces~round~628 D$
本场题解连接
$链接里的d题有详细题解$
AC代码

/*Author:zzugzxLang:C++Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);ll u,v;while(cin>>u>>v){if(v-u<0||(v-u)%2){cout<<-1<<endl;continue;}ll d=v-u;if(!d){if(!u)cout<<0;else cout<<1;}else{ll t=d/2;if((t&u)==0)cout<<2;else cout<<3;}cout<<endl;}return 0;
}

---

G.XOR

题意：
$已知n，从1到n中选任意两个数异或$
$这个异或的最大值为多少$
题解：
$最大值很明显尽量是让每个数都为1$
$那么比如n的二进制位101010100$
$那肯定是拿100000000和1111111异或$
$最后全部为1就是结果$
AC代码

/*Author:zzugzxLang:C++Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);ll n;cin>>n;if(n==1){cout<<0;return 0;}ll ans=0,cnt=0;while(n)ans+=(1ll<<cnt),cnt++,n>>=1;cout<<ans;return 0;
}

---

H.Maze

题意：
$n*m的图，图中包含+或者-$
$每个点能往四个方向和自己符号不同的位置走$
$q次询问，问从某个点开始最多能走向多少个不同点$
题解：
$只要符号不同就可以走$
$并且不限制来回，可以走过去的点也可以回来$
$所以完全可以对每个直接bfs$
$但是为了防止超时，所以考虑用并查集$
$相邻不同点在一个集合，只要是一个集合里的点都可以到达$
$所以只要查询每个点所在集合有多少点就是答案$
AC代码

/*Author:zzugzxLang:C++Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int n,m;
char g[3010][3010];
int fa[10000010],sz[10000010];
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
int id(int i,int j){return (i-1)*m+j;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int q;cin>>n>>m>>q;for(int i=1;i<=n*m;i++)fa[i]=i;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>g[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<4;k++){int dx=i+dir[k][0];int dy=j+dir[k][1];if(dx<1||dx>n||dy<1||dy>m||g[dx][dy]==g[i][j])continue;fa[find(id(i,j))]=find(id(dx,dy));}for(int i=1;i<=n*m;i++)sz[find(i)]++;for(int i=1;i<=n*m;i++)sz[i]=sz[find(i)];while(q--){int x,y;cin>>x>>y;cout<<sz[id(x,y)]<<endl;}return 0;
}

---

I.Prime

题意：
$q次询问，每次询问l到r中有多少个素数$
题解：
$l,r<=1e7$
$所以不能每次暴力查询$
$那么就用素数筛找出所有排好序的质数$
$然后用lower_bound和upper_bound进行边界查找$
$看数组中间有多少个即可$
AC代码

/*Author:zzugzxLang:C++Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};int prime[maxn];
bool isprime[10000010];
int num=0;
void Prime(int n){memset(isprime,true,sizeof(isprime));for(int i=2;i<=n;i++){if(isprime[i]) prime[++num]=i;for(int j=1;j<=num;j++){if(i*prime[j]>n) break;isprime[i*prime[j]]=false;if(i%prime[j]==0) break;}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);Prime(10000000);int _;cin>>_;while(_--){int l,r;cin>>l>>r;int p=lower_bound(prime+1,prime+1+num,l)-prime-1;int q=upper_bound(prime+1,prime+1+num,r)-prime-1;cout<<q-p<<endl;}return 0;
}

---

J.Compare

题意：
$给数a,b，如果a<b输出<$
$a==b输出=$
$a>b输出>$
题解：
$a,b<=10^{100000}$
$数很大，需要用高精度的判断$
$我这里直接用了python来写$
AC代码

a=int(input())
b=int(input())
if a>b :print('>')
elif a==b:print('=')
else :print('<')

---

K.Walk

题意：
$t次询问从1，1到n,m有多少种最短的走法~mod1e9+7$
题解：
$n,m<=1e6$
$按理说应该用dp进行转移$
$最短走法应该只往下和右走$
$dp[i][j]=dp[i-1][j]+dp[i][j-1]$
$但是这个n，m较大，不支持用二维数组和复杂度，并且还是多组输入$
$那么直接用组合数进行计算$
$从(1,1)到(n,m)的路径往右和往下总共走n+m-2次$
$其中往下走包括n-1次，那么直接C_{n+m-2}^{n-1}$
$从n+m-2步中选出n-1步往下走，剩下的步数往右走$
$所以直接预处理+逆元使用组合数$
AC代码

/*Author:zzugzxLang:C++Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e6+10;
const ll inf=0x3f3f3f3f;
const int dir[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
ll fact[maxn],inv1[maxn];
ll Pow(ll a, ll b){ll ans = 1;while(b > 0){if(b & 1){ans = ans * a % mod;}a = a * a % mod;b >>= 1;}return ans;
}
//逆元
ll inv(ll b){return Pow(b,mod-2)%mod;
}ll C(ll n,ll m){if(m>n||n<0||m<0)return 0;if(m==0||m==n) return 1;ll res=(fact[n]*inv1[m]%mod*inv1[n-m])%mod;return res;
}void init() {fact[0] = 1;for (int i = 1; i < maxn; i++) {fact[i] = fact[i - 1] * i %mod;}inv1[maxn - 1] = Pow(fact[maxn - 1], mod - 2);for (int i = maxn - 2; i >= 0; i--) {inv1[i] = inv1[i + 1] * (i + 1) %mod;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);init();int _;cin>>_;while(_--){int n,m;cin>>n>>m;cout<<C(n+m-2,n-1)<<endl;}return 0;
}

L. Defeat the monster

题意：
$给n个人，每个人都有能力值$
$要组一队人探险，这一队人能力极差不能超过5$
$问这一组最多可以有多少人$
题解：
$肯定需要先进行排序，然后选一段符合条件的连续子串$
$所以可以考虑用尺取方法去做$
$但是由于尺取写起来不好下手$
$所以我考虑的是lowerbound和upperbound进行查找$
$对每个数，查找他a_i-j到a_i+5-j之内的数$
$也就是以他为一个点找他附近符合条件的，找尽量大的长度$
AC代码

/*Author:zzugzxLang:C++Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};int a[maxn];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);int ans=0;for(int i=1;i<=n;i++){for(int j=0;j<=5;j++){int p=lower_bound(a+1,a+1+n,a[i]-j)-a-1;int q=upper_bound(a+1,a+1+n,a[i]+5-j)-a-1;p=max(0,p);q=min(n,q);ans=max(ans,q-p);}}cout<<ans;return 0;
}