挑战赛 #16 全题解

亚洲卷王 AK IOI

2025-04-06 14:56:48

发布于：北京

46阅读

0回复

0点赞

龟速AK，%%% 7_dp_[0][0]_3，%%% 🐱‍🚀 两位神仙

T1

显然地，我们知道了 $i,j,k,z,n$ 之后，可以求出 $p$ ，所以只需要一个四重循环。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(ll i=0;i<=n;i+=8){
        for(ll j=0;i+j<=n;j+=6){
            for(ll k=0;i+j+k<=n;k+=4){
                for(ll l=0;i+j+k+l<=n;l+=2){
                    ll m=n-i-j-k-l;
                    cout<<i/8<<' '<<j/6<<' '<<k/4<<' '<<l/2<<' '<<m<<'\n';
                }
            }
        }
    }
    return 0;
}

T2

看到质数有关的，先打一个欧拉筛上去。时间复杂度： $O(n)$ .

这样我们得到了所有不超过 $n$ 的质数。数位分离一下，计算和并取模即可。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25,MOD=1093;
ll n,ans,pcnt;
ll prm[MAXN];
bool isp[MAXN]={true,true};
int main(){
    cin>>n;
    for(ll i=2;i<=n;i++){
        if(!isp[i]) prm[++pcnt]=i;
        for(ll j=1;j<=pcnt;j++){
            if(i*prm[j]>n) break;
            isp[i*prm[j]]=true;
            if(i%prm[j]==0) break;
        }
    }
    for(ll i=1;i<=pcnt;i++){
        while(prm[i]){
            ans+=prm[i]%10;
            if(ans>=MOD) ans-=MOD;
            prm[i]/=10;
        }
    }
    cout<<ans;
    return 0;
}

T3

（显然的） $k$ 是 $A,B$ 的公约数。

所以我们枚举 $\gcd(A,B)$ 的所有约数就好了。

注意只枚举到 $\sqrt{\gcd(A,B)}$ 即可。因为约数成对出现。

特判完全平方数的情况。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
ll a,b,n;
vector<ll> ans;
int main(){
    cin>>a>>b;
    n=__gcd(a,b);
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            ans.eb(i);
            if(i*i<n) ans.eb(n/i);
        }
    }
    sort(ans.begin(),ans.end());
    for(auto &i:ans) cout<<i<<' ';
    return 0;
}

T4

枚举垂足点 $i$ 。

如果我们知道另一个点 $j$ ，那么我们可以知道构成直角三角形的点 $k$ 在某条直线上。

所以我们对于每一个 $j$ ，记录一下它的向量如何表示。

然后统计 $k$ 的数量。

由于三角形算了两遍，记得除以 $2$ 。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define mkp make_pair
#define fir first
#define sec second
ll n,ans;
pll t;
ll x[1505],y[1505];
map<pll,ll> mp;
inline pll slope(const ll &a,const ll &b){
    if(a==0&&b==0) return mkp(0,0);
    ll g=__gcd(a,b);
    ll aa=a/g,bb=b/g;
    if(aa<0||aa==0&&bb<0) aa=-aa,bb=-bb;
    return mkp(aa,bb);
}
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>x[i]>>y[i];
    for(ll i=1;i<=n;i++){
        mp.clear();
        for(ll j=1;j<=n;j++){
            if(i==j) continue;
            mp[slope(x[j]-x[i],y[j]-y[i])]++;
        }
        for(auto &it:mp){
            if(it.fir.fir==0) t=mkp(1,0);
            else if(it.fir.sec==0) t=mkp(0,1);
            else{
                t=mkp(-it.fir.sec,it.fir.fir);
                if(t.fir<0||t.fir==0&&t.sec<0) t=mkp(-t.fir,-t.sec);
            }
            ans+=mp[t]*it.sec;
        }
    }
    cout<<(ans>>1);
    return 0;
}

T5

首先我们对于每一个位置记录四方向是否可达。

我们知道，如果 {i,j) 可达 $(k,l)$ ，并且 $(k,l)$ 可达 $(i,j)$ ，那么我们才能从这里走过去。（观察样例解释可以得到）

这就很好写了。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define pll pair<ll,ll>
#define mkp make_pair
#define fir first
#define sec second
const ll MAXN=1e3+13;
ll n,m,s,res;
ll mx[]={0,1,0,-1},my[]={-1,0,1,0};
bool vis[MAXN][MAXN],edge[2][4][MAXN][MAXN];
vector<ll> ans;
inline void dfs(const ll &x,const ll &y){
    res++;
    ll nx,ny;
    for(ll i=0;i<4;i++){
        nx=x+mx[i],ny=y+my[i];
        if(nx<=0||ny<=0||nx>n||ny>m) continue;
        if(edge[1][i][x][y]) continue;
        ll j;
        if(i==0) j=2;
        else if(i==1) j=3;
        else if(i==2) j=0;
        else j=1;
        if(edge[1][j][nx][ny]) continue;
        if(!edge[0][i][x][y]) continue;
        if(vis[nx][ny]) continue;
        vis[nx][ny]=true;
        dfs(nx,ny);
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>s;
            for(ll k=0;k<4;k++){
                if(s>>k&1) edge[1][k][i][j]=true;
                else edge[0][k][i][j]=true;
            }
        }
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            if(vis[i][j]) continue;
            res=0;
            vis[i][j]=true;
            dfs(i,j);
            ans.eb(res);
        }
    }
    sort(ans.begin(),ans.end(),greater<ll>());
    for(auto &i:ans) cout<<i<<' ';
    return 0;
}

T6

普通的 DP 很容易想出来，刷表法就行了。

优化：注意到每一次跳跃的距离永远在 $[d-400,d+400]$ 之间，所以优化成 $O(800N)$ 能过了。

为什么？

我不知道啊，感觉是一个神秘的东西。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=3e4+34;
ll n,m,x,y,z,ans;
ll a[MAXN];
unordered_map<ll,ll> dp[MAXN];
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>x;
        a[x]++;
    }
    dp[m][0]=a[m];
    for(ll i=m;i<=30000;i++){
        for(ll j=-400;j<=400;j++){
            x=m+j;
            if(x<=0||!dp[i].count(j)) continue;
            for(ll k=-1;k<=1;k++){
                y=x+k;
                if(y<=0) continue;
                z=i+y;
                if(z<=30000){
                    dp[z][j+k]=max(dp[i][j]+a[z],dp[z][j+k]);
                    ans=max(dp[i][j]+a[z],ans);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}