1001.Total Eclipse

并查集维护求和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int d[N],f[N],fa[N],vis[N],num[N];
vector<int> g[N];
int cmp(int a,int b)
{
    return d[a]>d[b];
}
int find(int x)
{
    if(f[x]==x) return f[x];
    return f[x]=find(f[x]);
}
signed main()
{
    int t; 
    scanf("%d",&t);
    while(t--)
    {
        int n,m; 
        scanf("%d%d",&n,&m);    
        for(int i=1;i<=n;i++) 
            g[i].clear();
        for(int i=1;i<=n;i++) 
        {
            scanf("%d",&d[i]);
            f[i]=i;
            vis[i]=fa[i]=0;
            num[i]=i;
        }
        sort(num+1,num+1+n,cmp);
        for(int i=1;i<=m;i++) 
        {
            int a,b; 
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        for(int i=1;i<=n;i++)
        {
            int x=num[i];
            vis[x]=1;
            for(auto it:g[x])
            {
                if(!vis[it]) continue;
                int fy=find(it);
                if(fy==x) continue;
                fa[fy]=f[fy]=x;
            }
        }
        ll res=0;
        for(int i=1;i<=n;i++) 
        res+=d[i]-d[fa[i]];
        printf("%lld\n",res);
    }

1006.The Oculus

队友出的大数题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi acos(-1)
const int maxn=1e6+10;
const ll mod=1e15+7;
struct cc{
    ll x;
    int id;
}p[2*maxn];
ll f[2*maxn];
bool cmp(cc x,cc y)
{
    return x.x<y.x;
}
ll solve(ll x,ll y,ll z)
{
    int a[55]={},b[55]={},c[55]={},d[55]={};
    int la=0,lb=0,lc=0,n;        //保存为数组 
    while(x)
        a[la++]=x%10,x/=10;
    while(y)
        b[lb++]=y%10,y/=10;
    while(z)
        c[lc++]=z%10,z/=10;
    for(int i=0;i<la;i++)        //大数乘法 
    {
        for(int j=0;j<lb;j++)
        {
            d[i+j]+=a[i]*b[j];
        }
    }
    d[0]+=7,d[15]+=1;        //+mod 
    n=max(la+lb-1,16);            //进位 
    for(int i=0;i<n;i++)
    {
        d[i+1]+=d[i]/10;
        d[i]%=10;
    }
    while(d[n]>=10)
        d[n+1]+=d[n]/10,d[n]%=10,n++;
    for(int i=0;i<=n;i++)            //减去c 
    {
        if(d[i]>=c[i])
            d[i]-=c[i];
        else
        {
            int k=i+1;
            while(d[k]==0)
                k++;
            d[k]--;
            for(int j=i+1;j<k;j++)
                d[j]+=9;
            d[i]+=10;
            d[i]-=c[i];
        }
    }
    ll s=0;                        //取模 
    for(int i=n;i>=0;i--)
    {
        s*=10;
        s+=d[i];
        s%=mod;
    }
    //cout<<s<<endl;
    return s;
}
int main() 
{
    int t,x,y,z,a,b,c;
    f[1]=1,f[2]=2,p[1].x=1,p[2].x=2,p[1].id=1,p[2].id=2;            //费波纳希数列 
    for(int i=3;i<=2000003;i++)
    {
        f[i]=f[i-1]+f[i-2];
        f[i]%=mod;
        p[i].x=f[i];
        p[i].id=i;
    }
    sort(p+1,p+2000004,cmp);
    /*int nn=0;
    for(int i=2;i<=2000003;i++)
    {
        if(p[i].x==p[i-1].x)
            cout<<++nn<<endl;
    }*/
    ll s,n,m;
    cin>>t;
    while(t--)
    {
        n=0,m=0,s=0;
        scanf("%d",&x);                    //输入 
        for(int i=1;i<=x;i++)
        {
            scanf("%d",&a);
            n=n+f[i]*a;
            n%=mod;
        }
        scanf("%d",&y);
        for(int i=1;i<=y;i++)
        {
            scanf("%d",&b);
            m=m+f[i]*b;
            m%=mod;
        }
        scanf("%d",&z);
        for(int i=1;i<=z;i++)
        {
            scanf("%d",&c);
            s=s+f[i]*c;
            s%=mod;
        }
        //cout<<n<<' '<<m<<' '<<s<<endl; 
        //s=(n*m-s+mod)%mod;
        s=solve(n,m,s);                // 得到（a*b-c）%mod 
        int l=1,r=2000003,mid;            //二分找k 
        while(l<=r)
        {
            mid=(l+r)/2;
            if(p[mid].x<s)
                l=mid+1;
            else if(p[mid].x>s)
                r=mid-1;
            else
            {
                l=mid;
                break;
            }
        }
        /*while(p[l].x!=s)
        {
            if(p[l].x<s)
                l++;
            else
                l--;
        }*/
        printf("%d\n",p[l].id);
    }
    return 0;
}

1010.Lead of Wisdom

爆搜

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi acos(-1)
const int maxn=1e6+10;
const int mod=1e9+7;
ll mmax,a,b,c,d,s;
struct{
    int a,b,c,d;
}p[55][55];
void dfs(int k)
{
    if(k==0)
    {
        s=(100+a)*(100+b)*(100+c)*(100+d);
        mmax=max(s,mmax); 
        return ;
    }
    int flag=1;
    for(int i=1;i<=p[k][0].a;i++)
    {
        flag=0;
        a+=p[k][i].a;
        b+=p[k][i].b;
        c+=p[k][i].c;
        d+=p[k][i].d;
        dfs(k-1);
        a-=p[k][i].a;
        b-=p[k][i].b;
        c-=p[k][i].c;
        d-=p[k][i].d;
    }
    if(flag)
        dfs(k-1);
}
int main() 
{
    int t,n,k,a,b,c,d,e;
    cin>>t;
    while(t--)
    {
        mmax=0,a=0,b=0,c=0,d=0;
        scanf("%d %d",&n,&k);
        for(int i=0;i<=k;i++)
            p[i][0].a=0; 
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d %d %d %d",&e,&a,&b,&c,&d);
            p[e][++p[e][0].a].a=a;
            p[e][p[e][0].a].b=b;
            p[e][p[e][0].a].c=c;
            p[e][p[e][0].a].d=d;
        }
        dfs(k);
        printf("%lld\n",mmax);
    }
    return 0;
}