【GDUT-ACM】大灌水

难以容忍的两个WA
Problem C

int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            priority_queue<LL,vector<LL>,greater<LL> > que;
            CLEAR(a);
            scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++) scanf("%lld",&a[i]);
            sort(a,a+n);
            for(int i=1;i<=m;i++)
            {
                que.push(a[n-i]);
            }
            LL ans=a[n-1];
            for(int i=n-m-1;i>=0;i--)
            {
                LL k=que.top();
                que.pop();
                que.push(k+a[i]);
                ans=max(ans,k+a[i]);
            }
            printf("%lld\n",ans);
        }
    return 0;
}

Problem D

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=2e5;
const LL maxl=1e5+10;
const int inf=99999999;
const float eps=1e-3;
 
LL a[maxn];
bool vis[maxl];
int n,m;
vector<LL> vec;
 
void init();
void solve();
void outp();
 
void get_prime()
{
    vec.clear();
    CLEAR(vis);
    int k=0;
    for (int i = 2; i < maxl;i++)
        if(!vis[i])
        {
            k++;
            vec.push_back(i);
            for (int j = 1; i * j <= maxl; j++)
            {
            vis[i * j] = 1;
            }
        }
}
 
int getfac(LL n)
{
    if (n<2) return 0;
    int h=0,res=0;
    while(h<vec.size())
    {
        if (n%vec[h]==0) res++;
        while (n%vec[h]==0) n/=vec[h];
        h++;
    }
    return res;
}
 
LL pow2(LL n)
{
    if (n<=0) return 1;
    else if (n==1) return 2;
    else if (n&1)
    {
        int k=pow2((n-1)>>1);
        return (k*k)<<1;
    }
    else
    {
        int k=pow2(n>>1);
        return k*k;
    }
}
 
int main()
{
    get_prime();
    int T;
    LL n,m;
    scanf("%d",&T);
    while(T--)
        {
            scanf("%lld%lld",&n,&m);
            if (m%n) {printf("0\n");continue;}
            else if (n==1) {printf("1\n");continue;}
            LL t=m/n;
            //printf("%d\n",getfac(t));
            LL ans=pow2(getfac(t)-1);
            printf("%lld\n",ans);
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
 
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1113
    User: semprathlon
    Language: C++
    Result: Wrong Answer
****************************************************************/

=====================================
Problem F
罕见的PE，输出末尾不能有多余空格，防不胜防

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=200;
const int inf=99999999;
const float eps=1e-3;
 
int a[maxn];
 
void init();
void solve();
void outp();
 
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(a);
            scanf("%d%d",&n,&m);
            int mina=inf,h=0;
            for(int i=0;i<m;i++)
            {
                int k;
                scanf("%d",&k);
                if (k<mina)
                {
                    mina=k;
                    a[h++]=k;
                }
            }
            sort(a,a+h);
            int k=0;
            for(int i=1;i<=n;i++)
            {
                if (k<h-1&&a[k+1]<=i) k++;
                if (i<n) printf("%d ",a[k]);
                else printf("%d",a[k]);
            }
            puts("");
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
 
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1121
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1488 kb
****************************************************************/

Problem G

int main()
{
    while(~scanf("%d",&n))
        {
            int k=n/3;
            printf("%d\n",(n%3)?2*k+n%3-1:2*k);
        }
    return 0;
}

Problem E
裸的并查集

const int maxn=2e5;
const int inf=99999999;
const float eps=1e-3;
 
int f[maxn];
int n,m;
 
int getf(int n)
{
    if (f[n]==n) return n;
    else return f[n]=getf(f[n]);
}
 
bool unite(int u,int v)
{
    int x=getf(u);
    int y=getf(v);
    if (x!=y)
    {
        f[ y ]=x;return 1;
    }
    else return 0;
}
 
 
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(f);
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++) f[i]=i;
            for(int i=1;i<=m;i++)
            {
                int u,v;
                scanf("%d%d",&u,&v);
                unite(u,v);
            }
            int ans=-1;
            for(int i=1;i<=n;i++)
                if (f[i]==i) ans++;
            printf("%d\n",ans);
        }
    return 0;
}
 
/**************************************************************
    Problem: 1118
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:264 ms
    Memory:2264 kb
****************************************************************/

=====================
还有个来不及提交的！［个人原因，15：26才加入比赛
Problem H

const int maxn=2e4;
const int inf=99999999;
const float eps=1e-3;
const pair<int,int> p0=make_pair(0,0);

int a[maxn],f1[maxn],f2[maxn];
pair<int,int> g1[maxn],g2[maxn];

void init();
void solve();
void outp();


int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        CLEAR(a);
        CLEAR(f1);
        CLEAR(f2);
        CLEAR(g1);
        CLEAR(g2);
        scanf("%d",&a[1]);
        f1[1]=f2[1]=0;
        g1[1]=g2[1]=p0;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if (f1[i-1]<f2[i-1])
            {
                g1[i]=make_pair(a[i],g1[i-1].second);
                g2[i]=make_pair(g1[i-1].first,a[i]);
                f1[i]=f1[i-1]+abs(a[i]-g1[i-1].first);
                f2[i]=f2[i-1]+abs(a[i]-g1[i-1].second);
            }
            else
            {
                g1[i]=make_pair(a[i],g2[i-1].second);
                g2[i]=make_pair(g2[i-1].first,a[i]);
                f1[i]=f1[i-1]+abs(a[i]-g2[i-1].first);
                f2[i]=f2[i-1]+abs(a[i]-g2[i-1].second);
            }

        }
        printf("%d\n",min(f1[n],f2[n]));
    }
}