【ACUMTB个人赛】第一周题解

题目链接：https://vjudge.net/contest/153124

由于是中文题题意就不放了……

A题：

思路：每个点与（0,0）连线的中间点的个数是gcd（a,b），直接暴力会超时，所以换种思路：记录f[i]为gcd=i的个数，f[i]=(n/i)*(m/i)-i的倍数，之后就可以计算啦。

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

ll f[maxn];

int main(){
    ll n,m;
    ll ans=0;
    cin>>n>>m;
    if(n<m) swap(n,m);
    for(ll i=n;i>=1;i--){
        f[i]=(n/i)*(m/i);
        for(ll j=2*i;j<=n;j+=i)
            f[i]-=f[j];
        ans+=f[i]*(2*i-1);
    }
    cout<<ans<<endl;
    return 0;
}

B题：

思路：已知图的度序列，判断是否可图化。用havel定理判断，不可图化就输出NO，可图化就输出YES和邻接矩阵，由于此题是Special Judge所以只用输出一种邻接矩阵就行啦。

havel定理：给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。把序列排成不增序，即d1>=d2>=……>=dn，则d可简单图化当且仅当d’={d2-1，d3-1，……d(d1+1)-1， d(d1+2)，d(d1+3)，……dn}可简单图化。简单的说，把d排序后，找出度最大的点（设度为d1），把它与度次大的d1个点之间连边，然后这个点就可以不管了，一直继续这个过程，直到建出完整的图，或出现负度等明显不合理的情况。

实例：4 3 1 5 4 2 1和4 3 1 4 2 0是否可图化？

第一组数据，排序后为 5 4 4 3 2 1 1，出度最大的点为5，与度次大的点连边（4 4 3 2 1），之后去掉该点，序列排序后为 3 3 2 1 1 0，以此类推，2 1 1 0 0，0 0 0 0，即该度序列可以图化。

第二组数据，排序后为4 4 3 2 1 0，连边、去点、排序后为3 2 1 0 0，1 0 0 -1，出现负度，所以该度序列不可图化。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int maxn=15;

typedef pair<int,int> P;

vector<P> v;
int mp[maxn][maxn];

int cmp(const P &a,const P &b){
    return a.first>b.first;
}

int n;

bool judge(){
    while(!v.empty()){
        sort(v.begin(),v.end(),cmp);
        if(v[0].first>=v.size()) return false;
        for(int i=1;i<=v[0].first;++i){
            --v[i].first;
            if(v[i].first<0) return false;
            mp[v[0].second][v[i].second]=mp[v[i].second][v[0].second]=1;
        }
        v.erase(v.begin());
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        v.clear();
        memset(mp,0,sizeof(mp));
        cin>>n;
        for(int i=0;i<n;i++){
            int tem;cin>>tem;
            v.push_back(make_pair(tem,i));
        }
        bool right=judge();
        if(right){
            cout<<"YES"<<endl;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    cout<<mp[i][j]<<" ";
                }
                cout<<endl;
            }
        }
        else cout<<"NO"<<endl;
        cout<<endl;
    }
    return 0;
}

C题：

思路：优先队列模拟。按优先级从小到大，优先级相等的情况下起始时间从大到小放入优先队列，对于第i个进程，如果i的起始时间与i-1的结束时间的时间差能够被优先队列中的堆顶进程完全使用（即堆顶进程的持续时间len<=时间差），则该进程的结束时间在这个时间差内，否则len-时间差并重新放回优先队列中。

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef pair<int,int> P;

const int maxn=3e5+10;
const int inf=1e9;

int start[maxn],slen[maxn],prv[maxn];

struct node{
    int id,len;
    bool operator <(const node&a) const{
        if(prv[id]==prv[a.id]) return start[id]>start[a.id];
        return prv[id]<prv[a.id];
    }
};

P ans[maxn];

priority_queue<node> q;

int cmp(const P&a,const P&b){return a.second<b.second;}

int main(){
    int id;
    while(scanf("%d",&id)!=EOF){
        scanf("%d %d %d",&start[id],&slen[id],&prv[id]);
        ans[id].first=id;
    }
    start[id+1]=inf;
    int now=0;
    for(int i=1;i<=id+1;i++){
        int len=start[i]-now;
        while(!q.empty()&&q.top().len<=len){
            now+=q.top().len;
            ans[q.top().id].second=now;
            len-=q.top().len;
            q.pop();
        }
        if(i==id+1) break;
        if(!q.empty()&&len){
            node tmp=q.top();q.pop();
            tmp.len-=len;
            q.push(tmp);
        }
        now=start[i];
        q.push((node){i,slen[i]});
    }
    sort(ans+1,ans+id+1,cmp);
    for(int i=1;i<=id;i++){
        printf("%d %d
",ans[i].first,ans[i].second);
    }
    return 0;
}

D题：

思路：LIS（最长上升子串，动态规划）的做法，如果i能够被j（i>j）在限时内抵达，则i可以被j转移。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

const int maxn=10005;

int dp[maxn],x[maxn],y[maxn],t[maxn];

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&t[i],&x[i],&y[i]);
    }
    dp[1]=1;int ans=1;
    for(int i=2;i<=m;i++){
        dp[i]=1;
        for(int j=1;j<=i-1;j++){
            if(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(ans,dp[i]);
    }
    printf("%d
",ans);
    return 0;
}

E题：

思路：由于1e6的数据量，可以从小到大枚举M，判断同余方程Pi-Pj≡Cj-Ci(mod M)是否成立，如果对于每组i，j都不成立，则M为最小的整数解。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=100;

int exgcd(int a,int b,int &x,int &y){
    if(b==0){x=1,y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int C[maxn],P[maxn],L[maxn];
int n;

bool solve(int b){
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            int a=((P[i]-P[j])%b+b)%b,m=((C[j]-C[i])%b+b)%b,x,y,d;
            d=exgcd(a,b,x,y);
            if(m%d!=0) continue;
            m/=d;
            int bb=b/d;
            int num=(m*x%bb+bb)%bb;
            if(num<=min(L[i],L[j])) return false;
        }
    }
    return true;
}

int main(){
    int mx=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>C[i]>>P[i]>>L[i];
        mx=max(C[i],mx);
        C[i]--;
    }
    for(int i=mx;;i++){
        if(solve(i)){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}