@[TOC]
比赛试题
A 最短路
B 组队
题解：
先排序，然后二分查找比当前数a[i]大k的第一个数坐标是多少，假设坐标是j，那么j之后的都要比i大k，只有j之前，i之后的符合题意，i与j有j-i个数，求最大值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+4;
ll a[maxn];
int main()
{
int t;
cin>>t;
ll n,k;
while(t--)
{
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
int sum=0;
int ans=-1;
for(int i=1;i<=n;i++)
{
sum=upper_bound(a+1,a+n+1,a[i]+k)-a;
ans=max(ans,sum-i);
}
cout<<ans<<endl;
}
return 0;
} C 十面埋伏
我一开始想直接在#周围标记，然后输出就行，
发现会存在#围成密闭空间，那么空间里就不用围起来
我又发现围起来的部分都是最左边#的左边，最上边#的上边，最右边#的右边，最下边#的下边，样例1能过，但数据过不了一半，因为如果有深沟处理不了，如样例2
#include<bits/stdc++.h>
using namespace std;
char a[505][505];
int maxx[505],minn[505];
int main()
{
int n,m;
cin>>n>>m;
char ch=getchar();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
ch=getchar();
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]=='#')
{
a[i][j-1]='*';
break;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
if(a[i][j]=='#')
{
a[i][j+1]='*';
break;
}
}
}
for(int j=1;j<=m;j++)
{
for(int i=1;i<=n;i++)
{
if(a[i][j]=='#')
{
a[i-1][j]='*';
break;
}
}
}
for(int j=1;j<=m;j++)
{
for(int i=n;i>=1;i--)
{
if(a[i][j]=='#')
{
a[i+1][j]='*';
break;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<a[i][j];
}
cout<<endl;
}
} 最后我才意识到，要把#周围全处理，其实直接dfs'.'
就是把圈外的'.'格dfs，然后标记，‘#’旁边被标记过的'.'格子就可以改成‘*’
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
int n,m;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char a[maxn][maxn];
bool vis[maxn][maxn];
void dfs(int x,int y){
vis[x][y]=true;
for(int i=0;i<4;i++){
int tx=x+dx[i];
int ty=y+dy[i];
if(vis[tx][ty]||tx<1||tx>n||ty<1||ty>m||a[tx][ty]!='.') continue;
dfs(tx,ty);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
dfs(1,1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]=='#')
{
for(int k=0;k<4;k++)
{
int tx=i+dx[k];
int ty=j+dy[k];
if(vis[tx][ty]) a[tx][ty]='*';
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<a[i][j];
}
cout<<endl;
}
return 0;
}
D 牛妹吃豆子
E 旅旅旅游
F 斗兽棋
大大大模拟。。
直接if比较就可以，因为这四个首字母不一样，直接首字母比较就可以。对了如果出的两个动物没有关系，也算平局
最后记住：舔狗一无所有！！！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+4;
string s1="tiangou txdy";
string s2="tiangou yiwusuoyou";
int main()
{
string w1,w2;
cin>>w1>>w2;
if(w1[0]=='e'&&w2[0]=='t')cout<<s2;
else if(w1[0]=='t'&&w2[0]=='c')cout<<s2;
else if(w1[0]=='c'&&w2[0]=='m')cout<<s2;
else if(w1[0]=='m'&&w2[0]=='e')cout<<s2;
else if(w2[0]=='e'&&w1[0]=='t')cout<<s1;
else if(w2[0]=='t'&&w1[0]=='c')cout<<s1;
else if(w2[0]=='c'&&w1[0]=='m')cout<<s1;
else if(w2[0]=='m'&&w1[0]=='e')cout<<s1;
else if(w1[0]=='e'&&w2[0]=='e')cout<<s2;
else if(w1[0]=='t'&&w2[0]=='t')cout<<s2;
else if(w1[0]=='c'&&w2[0]=='c')cout<<s2;
else if(w1[0]=='m'&&w2[0]=='m')cout<<s2;
else cout<<s2;
return 0;
} G 做题
我一开还以为会存在性价比比较什么的，后来发现想多了。。
排个序从小开始算就完事了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+4;
int a[maxn];
int main()
{
long long n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+1+n);
int sum=0;
for(int i=1;i<=n;i++)
{
if(m-a[i]>=0)sum++;
else break;
m-=a[i];
}
printf("%lld",sum);
return 0;
} H 人人都是好朋友
第一眼过去并查集，将有关的人联系在一起，判断时直接查询是否为父亲节点是否相同
注意a和b的范围远大于n，说明小弟不可能都登场，我们只需要小弟们的相对大小，即能区分开就行，所以离散化处理
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e6 + 3;
int father[maxn];
int T;
int a[maxn];
int b[maxn];
int c[maxn];
int d[maxn];
int n;
bool f;
int find(int x)
{
if(father[x]!=x)return father[x]=find(father[x]);
else father[x];
}
void lisanhua(int tot)
{
sort(d + 1, d + tot + 1);
tot = unique(d + 1, d + tot + 1) - d;
for (int i = 1; i <= n; i++)
{
a[i] = lower_bound(d + 1, d + tot + 1, a[i]) - d;
b[i] = lower_bound(d + 1, d + tot + 1, b[i]) - d;
}
}
void init(int tot)
{
for (int i = 1; i <= tot; i++)father[i] = i;
}
void unionn(int i)
{
father[find(a[i])]=find(b[i]);
}
bool iff(int i)
{
if(find(a[i])==find(b[i]))return 1;
else return 0;
}
int main()
{
scanf("%d",&T);
while (T--)
{
cin >> n;
f = 1;
int tot = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
d[++tot] = a[i];
d[++tot] = b[i];
}
lisanhua(tot);//离散化
init(tot);//初始化
for (int i = 1; i <= n; i++)
{
if (c[i])unionn(i);
}
for (int i = 1; i <= n; i++)
{
if (!c[i])
if(iff(i))f = 0;
}
if (f)
cout<<"YES";
else
cout<<"NO";
}
return 0;
} I 求和
DFS序加线段树（或者树状数组）维护
代码略
J 建设道路
直接做n^2^肯定超时，需要优化，我们可以将公式一步步转化，最后转成O(n)
pre[]为a[i]的前缀和
pre1[]为a[i]^2^的前缀和
O（n）就可以算出
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=5e5+4;
ll a[maxn];
ll pre[maxn];
ll pre1[maxn];
ll sum;
ll ans1,ans2,ans3,ans;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
pre[i]=(pre[i-1]+a[i])%mod;
pre1[i]=(pre1[i-1]+a[i]*a[i])%mod;
}
for(int i=1;i<=n;i++)
{
ans1 = ((n - i) * ((a[i] * a[i]) % mod)) % mod;
ans2 = ((2 * a[i]) % mod) * ((pre[n] - pre[i] + mod) % mod) % mod;
ans3 = (pre1[n] - pre1[i]+mod) % mod;
ans = (ans1 - ans2 + ans3+mod) % mod;
sum=(sum+ans)%mod;
}
printf("%lld",sum);
return 0;
} 还有其他推法解法，但是我没看懂。。。我太弱了
京公网安备 11010502036488号