挑战赛 #7 题解
2024-08-07 17:16:37
发布于：上海
81阅读
0回复
0点赞
本次挑战赛的难度有挑战赛的难度。听君一席话，如听一席话
T1
直接拓扑排序一下即可。注意可能有非 源点，需要把这些点的路径数量设为 再加入搜索队列，时间复杂度 。
#include <cstdio>
#include <memory.h>
#include <queue>
using namespace std;
vector<int>g[5005];
int ind[5005],cnt[5005];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k;scanf("%d",&k);
for(int j=1;j<=k;j++){
int b;
scanf("%d",&b);
g[i].push_back(b);
ind[b]++;
}
}
queue<int>q;
q.push(1);cnt[1]=1;
for(int i=2;i<=n;i++){
if(ind[i]==0){
q.push(i);
cnt[i]=0;
}
}
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<g[x].size();i++){
cnt[g[x][i]]+=cnt[x];
cnt[g[x][i]]%=114514;
ind[g[x][i]]--;
if(ind[g[x][i]]==0) q.push(g[x][i]);
}
}
printf("%d",cnt[n]%114514);
return 0;
}
T2
无论如何旋转都一样，相当于对于每一个 ，都有 。因此，我们考虑将这些字符中的最大值分别减去每一个字符，得到的结果即为让这四个字符相同需要的操作次数。时间复杂度 。
#include <cstdio>
#include <algorithm>
using namespace std;
char a[1005][1005];
int main(){
int T;scanf("%d",&T);while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
long long ans=0;
for(int i=1;i<=n>>1;i++)
for(int j=1;j<=n>>1;j++)
ans+=(max(max(a[i][j],a[j][n-i+1]),max(a[n-j+1][i],a[n-i+1][n-j+1]))<<2)-a[i][j]-a[j][n-i+1]-a[n-j+1][i]-a[n-i+1][n-j+1];
printf("%lld\n",ans);
}
return 0;
}
T3
考虑对 条件进行变换：。因此我们可以求出对于每一个 的 ，并对其进行桶计数。容易得出，若一个桶内有 个元素，则这个桶对答案的贡献为 。时间复杂度 。
实现时有一些小细节：答案要开 long long，并且桶可能被放入负数，可以考虑对每一个放入桶中的元素都 。
#include <cstdio>
#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
#include <cmath>
#include <memory.h>
#define map unordered_map
#define ll long long
#define ull unsigned long long
using namespace std;
namespace io{
const int size=(1<<20)+1;
char buf[size],*p1=buf,*p2=buf;
char buffer[size];
int op1=-1;
const int op2=size-1;
inline char readchar() {
if(p1!=p2) {
return *p1++;
}
return p1==(p2=(p1=buf)+fread(buf,1,size-1,stdin))?EOF:*p1++;
}
inline void flush() {
fwrite(buffer,1,op1+1,stdout),op1=-1;
}
inline void writechar(const char &x) {
if(op1==op2) flush();
buffer[++op1]=x;
}
#define gc readchar
#define pc writechar
#define el pc(10)
#define sp pc(32)
inline int readi(){
int x=0;bool w=0;
char ch=gc();
while(ch<'0'||ch>'9'){
if(ch=='-') w=1;
ch=gc();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=gc();
}
return w?-x:x;
}
inline ll readl(){
ll x=0;bool w=0;
char ch=gc();
while(ch<'0'||ch>'9'){
if(ch=='-') w=1;
ch=gc();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=gc();
}
return w?-x:x;
}
void writei(int x){
if(x<0) pc('-'),x=-x;
if(x>9) writei(x/10);
pc((x%10)^48);
}
void writel(ll x){
if(x>9) writel(x/10);
pc((x%10)^48);
}
};// io
using namespace io;
#define prc(x) printf(#x":%c\n",x)
#define pri(x) printf(#x":%d\n",x)
#define prl(x) printf(#x":%lld\n",x)
int b[400005];
int main(){
int n=readi();
for(register int i=1;i<=n;i++)
b[readi()-i+200000]++;
long long ans=0;
for(register int i=1;i<=n+200000;i++)
ans+=(b[i]*(b[i]-1))>>1;
writel(ans);flush();
return 0;
}
T4
直接广搜即可，步长分别为 。时间复杂度 。
#include <cstdio>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <unordered_map>
#include <cmath>
#include <memory.h>
#include <cstring>
#define map unordered_map
using namespace std;
#define prc(x) printf(#x":%c\n",x)
#define pri(x) printf(#x":%d\n",x)
#define prl(x) printf(#x":%lld\n",x)
#define ll long long
#define ull unsigned long long
#define check(x,y) (x>=0&&x<=500&&y>=0&&y<=500)
struct node{int x,y;};
int dx[]={-2,-2,2,2},
dy[]={-2,2,-2,2};
int vis[505][505];
int main(){
int n,a,b,c,d;scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
vis[a][b]=1;
queue<node>q;q.push({a,b});
while(!q.empty()){
int x=q.front().x,y=q.front().y;q.pop();
if(x==c&&y==d){
puts("YES");
return 0;
}
for(int i=0;i<=3;i++){
int nx=x+dx[i],ny=y+dy[i];
if(check(nx,ny)&&!vis[nx][ny]){
vis[nx][ny]=1;
q.push({nx,ny});
}
}
}
puts("NO");
return 0;
}
T5
发现 的数据范围极小，考虑暴力搜索。直接深搜即可。发现答案差值不会太大（不会超过 ），为了避免爆 long long，可以在 过大（大约 ）时直接剪枝即可。但是过程中仍然可能爆 long long（ 位乘 位时），由于我不想写高精度，就用了 long long long long__int128。时间复杂度（大约） 。
#include <cstdio>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <unordered_map>
#include <cmath>
#include <memory.h>
#include <cstring>
#define map unordered_map
using namespace std;
#define prc(x) printf(#x":%c\n",x)
#define pri(x) printf(#x":%d\n",x)
#define prl(x) printf(#x":%lld\n",x)
#define ll long long
#define ull unsigned long long
#define llll __int128
ll ans=1ll<<48;
llll inf=1ll<<48;
int l1[15],r1[15],n;
void dfs(int x,llll l,llll r){
// pri((int)x);
if(l>inf) return;
if(x==n+1){
ans=min(ans,abs((ll)(l-r)));
return;
}
for(int i=x+1;i<=n;i++){
dfs(i,l*l1[i],r+r1[i]);
}
if(x!=0)dfs(n+1,l,r);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",l1+i,r1+i);
dfs(0,1,0);
printf("%lld",ans);
return 0;
}
T6
好吧，这次的签到题竟然事 T6，让我想起了某届欢乐赛。
思路：找到 ? 所处的那一行，然后看那一行少了哪个字母。
int main(){
char s[4][4];
scanf("%s%s%s",s[1]+1,s[2]+1,s[3]+1);
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
if(s[i][j]=='?'){
char c1=s[i][1],c2=s[i][2],c3=s[i][3];
// printf("%c%c%c",c1,c2,c3);
if(c1=='?') c1=c3;
if(c2=='?') c2=c3;
if(c1>c2) swap(c1,c2);
if(c1!='A') putchar('A');
else if(c2!='C') putchar('C');
else putchar('B');
}
}
}
return 0;
}
后记
好吧，你说得对，但是这篇题解确实都是在集训营里肝出来的，所以非常生草。
有帮助，赞一个