2019 Multi-University Training Contest 8

1003 Acesrc and Good Numbers

题目链接
题意：定义F(d,n)为从1—n中包含d的个数，求给你d和x，求寻找最大的n小于x且满足F(d,n)=n。
思路：对于F(d,n)我们可以通过数位DP得到，设ans=F(d,n),设sub=|n-ans|代表从1—n中d的个数总和与现在数的差值。可知减少每个数至多减少18个d（999—>998减少了3个9），故sub/18可以看作代表至多减少的d的个数。

题解中证明这样的数只存在在1e11内。oeis上也可以找到满足的数据列表。
题解想法是在暴力搜索的基础上进行剪枝。

#include <bits/stdc++.h>

#define maxn 20
typedef long long ll;
using namespace std;

int d;ll x;
ll ans=0;
int cnt;
int lim[maxn];
ll p[maxn];
ll num[maxn];

ll calc(int pos){
    if(pos<=0)return 0;
    return 1ll*pos*p[pos-1];
}

void dfs(int d,int index){
    if(index==0)return;

    for(int i=0;i<lim[index];i++){
        if(i==d)
            ans+=p[index-1];
        ans+=calc(index-1);
    }

    if(lim[index]==d){
        ans+=num[index-1]+1;
    }

    dfs(d,index-1);
}

void solve(int d,ll x){
    ans=0;
    cnt=0;
    p[0]=1;
    while(x){
        lim[++cnt]=x%10;
        p[cnt]=p[cnt-1]*10;
        x/=10;
    }

    for(int i=1;i<=cnt;i++)
        num[i]=num[i-1]+lim[i]*p[i-1]; 

    dfs(d,cnt);
}

void input(){
    scanf("%d%lld",&d,&x);
    solve(d,x);
    while(ans!=x){
        x-=1ll*ceil(1.0*abs(ans-x)/18);
        solve(d,x);
    }

    printf("%lld\n",x);
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
    }
}

1008 Andy and Maze

题目链接
题意：给出一张图，n个点，m条边。寻找从任意点出发，走k步的最大边权和。
思路：对于每一个点进行搜索，记录所有边中的最大边权，当现边权和+剩余步数*最大边权<=已经记录的最大边权和，就剪枝。
参考
不会算此解法的时间复杂度。

#include <bits/stdc++.h>

#define maxn 10005
using namespace std;

int n,m,k;
int ans,maxx;
struct edge{
    int to,cost;
};
vector <edge>G[maxn];
int vis[maxn];

void dfs(int x,int step,int tot){
    if(step==k)
    {
        ans=max(ans,tot);
        return;
    }

    if(tot+(k-step)*maxx<=ans)
        return;

    for(int i=0;i<G[x].size();i++){
        if(!vis[G[x][i].to]){
            vis[G[x][i].to]=1;
            dfs(G[x][i].to,step+1,tot+G[x][i].cost);
            vis[G[x][i].to]=0;
        }
    }
}

void input(){
    scanf("%d%d%d",&n,&m,&k);
    int i;
    for(i=1;i<=n;i++){
        G[i].clear();
        vis[i]=0;
    }

    ans=maxx=-1;
    int u,v,w;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        G[u].emplace_back((edge){v,w});
        G[v].emplace_back((edge){u,w});
        maxx=max(maxx,w);
    }
}

void solve(){
    for(int i=1;i<=n;i++){
        vis[i]=1;
        dfs(i,1,0);
        vis[i]=0;
    }

    if(ans==-1)
        printf("impossible\n");
    else
        printf("%d\n",ans);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();    
    }
}

1009 Calabash and Landlord

题目链接
题意：在一个无限大小的平面用两个矩形框出若干给联通块，求连通块个数。
思路：将坐标哈希后，对于两个联通块涂色，计算同颜色的联通块个数，最后加一。哈希后的点坐标要转化为块的坐标。

#include <bits/stdc++.h>

using namespace std;

int x[4],y[4];
int xCopy[4],yCopy[4];
int sizeX,sizeY;
int g[5][5];
int book[5][5];

void input(){
    scanf("%d%d%d%d",&x[0],&y[0],&x[1],&y[1]);
    scanf("%d%d%d%d",&x[2],&y[2],&x[3],&y[3]);
}

void Init_Hash_x(){
    int i;
    for(i=0;i<4;i++)
        xCopy[i]=x[i];

    sort(xCopy,xCopy+4);
    sizeX=unique(xCopy,xCopy+4)-xCopy;
}

int Hash_x(int x){
    return lower_bound(xCopy,xCopy+sizeX,x)-xCopy+1;
}

void Init_Hash_y(){
    int i;
    for(i=0;i<4;i++)
        yCopy[i]=y[i];

    sort(yCopy,yCopy+4);
    sizeY=unique(yCopy,yCopy+4)-yCopy;
}

int Hash_y(int x){
    return lower_bound(yCopy,yCopy+sizeY,x)-yCopy+1;
}

struct node{
    int x,y;
};

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

void BFS(int x,int y){
    book[x][y]=1;
    queue <node>q;
    node temp;
    temp.x=x;temp.y=y;
    q.push(temp);

    while(!q.empty()){
        node f=q.front();
        q.pop();

        for(int i=0;i<4;i++){
            int tx=f.x+dx[i];
            int ty=f.y+dy[i];

            if(tx>=1&&tx<=sizeX&&ty>=1&&ty<=sizeY&&!book[tx][ty]&&g[tx][ty]==g[f.x][f.y])
            {
                book[tx][ty]=1;
                temp.x=tx;temp.y=ty;
                q.push(temp);
            }
        }
    }
}

void solve(){
    Init_Hash_x();
    Init_Hash_y();

    int i,j;
//    cout<<endl;
//    for(i=0;i<4;i++)
//        cout<<Hash_x(x[i])<<' '<<Hash_y(y[i])<<endl;
//    cout<<endl;

    memset(g,0,sizeof g);
    for(i=Hash_x(x[0]);i<Hash_x(x[1]);i++)
        for(j=Hash_y(y[0]);j<Hash_y(y[1]);j++)
            g[i][j]+=1;

    for(i=Hash_x(x[2]);i<Hash_x(x[3]);i++)
        for(j=Hash_y(y[2]);j<Hash_y(y[3]);j++)
            g[i][j]+=2;

//    for(i=1;i<=4;i++){
//        for(j=1;j<=4;j++)
//            cout<<g[i][j];
//        cout<<endl;
//    }

    memset(book,0,sizeof book);
    int ans=1;
    for(i=1;i<=4;i++)
        for(j=1;j<=4;j++)
            if(!book[i][j]&&g[i][j])
            {
//                cout<<i<<' '<<j<<endl;
                BFS(i,j);
                ans++;
            }

    printf("%d\n",ans);
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();
    }
}

1010 Quailty and CCPC

题目链接
题意：比赛规定了d*10%的队伍数可以归为金牌，当这个金牌队伍数num的小数部分为0.5时，我们可以对第num+1的队伍进行申请，让其从银牌变为金牌。题目求是否存在这样队伍，输出其名称
思路：排序后，判断小数部分是否为0.5，找到队伍名即可。

#include <bits/stdc++.h>

#define maxn 100005
typedef long long ll;
using namespace std;

int n,d;
struct team{
    char name[20];
    int p,t;
}te[maxn];

bool cmp(team a,team b){
    if(a.p==b.p)
        return a.t<b.t;
    return a.p>b.p;
}

void input(){
    int i;
    scanf("%d%d",&n,&d);
    for(i=0;i<n;i++){
        scanf("%s%d%d",&te[i].name,&te[i].p,&te[i].t);
    }

    sort(te,te+n,cmp);    
}

bool check(int n,int d){
    ll ans=1ll*n*d;
    if(ans%10==5)
        return 1;
    else
        return 0;
}

void solve(){
    int num=n*d/10;
    if(check(n,d)){
        printf("%s\n",te[num]);
    }else
        printf("Quailty is very great\n");
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();
    }
}

1011 Roundgod and Milk Tea

题目链接
题意：每个班级有ai个人制作bi个奶茶，每个班的人只能喝别班的奶茶，求最后能喝的总人数
思路：记sum为所有班人数总和，对于每个班制作的奶茶bi，其能分给sum-ai的人。我们取min(bi,sum-ai)代表每个班分给其他班人的奶茶数，其相加得到总和SUM，代表我一共分出的奶茶数，当SUM>=sum时代表，分出的奶茶数大于所有班人数，故答案应为sum。当SUM<sum时，代表我分出的奶茶数小于所有班的人数，其中可能存在重复部分，但可以通过更改分配方式(二分图最优匹配)使得分出的奶茶数都最优，题目不要求寻找这种匹配方式，只需知道分出的奶茶数即为所求答案。