2019杭电多校第八场

1004 Acesrc and Hunting

很遗憾由于没有考虑到$n$和$m$的大小关系导致赛后五分钟补题。。。
首先构造$2\ast k$的形式
$0123456$
$abcdefg$
当k是奇数时，顺序为$0b2d4g5e6f3c1a$
$01234567$
$abcdefgh$
当k是偶数时，顺序为$0b2d4f6h57ge3c1a$
反正就是互相取，在顶部绕一下就好
这样绕完之后就从0变到了a，也就是第一行开始，第二行结束
那么第二组就要第四行开始，第三行结束（对称）
考虑最后多一行怎么办？尝试构造$3\ast k$
$01234567$
$abcdefgh$
$xyxxxxx$
$xxxxxxx$
$xxxxxxx$
假设现在要填最后三行，注意无论在0结束还是在a结束，都可以跳到y处
如果k是奇数，就先放入如下一组：
$714$
$63(9)$
$285$
否则就先放如下一组：
$41$
$2(6)$
$53$
这样构造的原因是为了两种起始状态的结束点都在正中间（括号处），因此接下来构造若干组：
$52$-$52$-…
$36$-$36$-…
$14$-$14$-…
即可

#include<bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
int T,n,m,l,r,tot,num,i,j,x,y,flag;
int f[105][105],g[105][105],res1[10005],res2[10005];
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        if (n > m) {swap(n,m); flag = 1;} else flag = 0;
        if (n == 1 && m == 1) {cout<<"YES"<<endl; cout<<"1 1"<<endl; continue;}
        if (n == 1 || m == 1) {cout<<"NO"<<endl; continue;}
        if (n == 2 && m == 2) {cout<<"NO"<<endl; continue;}
        if (n % 2 == 0) num = n / 2; else num = (n - 3) / 2;
        tot = 0;
        l = 1; r = 2;
        while (num--)
        {
            if (m % 2 == 0)
            {
                fo(i,1,m) if (i % 2 == 1) f[l][i] = ++tot; else f[r][i] = ++tot;
                f[l][m-2] = ++tot; f[l][m] = ++tot;
                f[r][m-1] = ++tot;
                fd(i,m-3,1) if (i % 2 == 1) f[r][i] = ++tot; else f[l][i] = ++tot;
            }    else
            {
                fo(i,1,m-2) if (i % 2 == 1) f[l][i] = ++tot; else f[r][i] = ++tot;
                f[r][m] = ++tot; f[l][m-1] = ++tot; f[r][m-2] = ++tot;
                f[l][m] = ++tot; f[r][m-1] = ++tot;
                fd(i,m-3,1) if (i % 2 == 0) f[l][i] = ++tot; else f[r][i] = ++tot;
            }
            if (l < r) {r += 1; l += 3;} else {l += 1; r += 3;}
        }
        if (n == 3)
        {
            if (m == 3)
            {
                x=1; y=1; f[x][y] = ++tot;
                x+=2; y++; f[x][y] = ++tot;
                x-=2; y++; f[x][y] = ++tot;
                x++; y--; f[x][y] = ++tot;
                x++; y--; f[x][y] = ++tot;
                x-=2; y++; f[x][y] = ++tot;
                x+=2; y++; f[x][y] = ++tot;
                x--; y-=2; f[x][y] = ++tot;
                y+=2; f[x][y] = ++tot;
            }    else
            {
                x=1; y=1; f[x][y] = ++tot;
                x+=2; y++; f[x][y] = ++tot;
                x--; y--; f[x][y] = ++tot;
                x--; y++; f[x][y] = ++tot;
                x+=2; y--; f[x][y] = ++tot;
                x--; y++; f[x][y] = ++tot;
                if (m % 2 == 0) num = m / 2 - 1; else num = (m-3) / 2 - 1;
                while (num--)
                {
                    x++; y++; f[x][y] = ++tot;
                    x-=2; y++; f[x][y] = ++tot;
                    x++; y--; f[x][y] = ++tot;
                    x++; y++; f[x][y] = ++tot;
                    x-=2; y--; f[x][y] = ++tot;
                    x++; y++; f[x][y] = ++tot;
                }
                if (m % 2 == 1)
                {
                    x++; y++; f[x][y] = ++tot;
                    x--; y++; f[x][y] = ++tot;
                    x--; y++; f[x][y] = ++tot;
                    x++; y-=2; f[x][y] = ++tot;
                    x++; y++; f[x][y] = ++tot;
                    x--; y++; f[x][y] = ++tot;
                    x--; y--; f[x][y] = ++tot;
                    x+=2; y++; f[x][y] = ++tot;
                    x-=2; y-=2; f[x][y] = ++tot; 
                }
            }
        }
        if (n != 3 && n % 2 == 1)
        {
            if (m == 3)
            {
                x = n-2; y = 2; f[x][y] = ++tot;
                x+=2; y++; f[x][y] = ++tot;
                x--; y--; f[x][y] = ++tot;
                x--; y--; f[x][y] = ++tot;
                x++; y+=2; f[x][y] = ++tot;
                x++; y--; f[x][y] = ++tot;
                x--; y--; f[x][y] = ++tot;
                x--; y+=2; f[x][y] = ++tot;
                x+=2; y-=2; f[x][y] = ++tot;
            }    else
            {
                f[n-2][2] = ++tot; f[n-1][1] = ++tot; f[n][2] = ++tot;
                f[n-2][1] = ++tot; f[n][1] = ++tot; f[n-1][2] = ++tot;
                if (m % 2 == 0) num = m / 2 - 1; else num = (m-3) / 2 - 1;
                x = n-1; y = 2;
                while (num--)
                {
                    x++; y++; f[x][y] = ++tot;
                    x-=2; y++; f[x][y] = ++tot;
                    x++; y--; f[x][y] = ++tot;
                    x++; y++; f[x][y] = ++tot;
                    x-=2; y--; f[x][y] = ++tot;
                    x++; y++; f[x][y] = ++tot;
                }
                if (m % 2 == 1)
                {
                    x++; y++; f[x][y] = ++tot;
                    x--; y++; f[x][y] = ++tot;
                    x--; y++; f[x][y] = ++tot;
                    x++; y-=2; f[x][y] = ++tot;
                    x++; y++; f[x][y] = ++tot;
                    x--; y++; f[x][y] = ++tot;
                    x--; y--; f[x][y] = ++tot;
                    x+=2; y++; f[x][y] = ++tot;
                    x-=2; y-=2; f[x][y] = ++tot; 
                }
            }    
        }
        fo(i,1,n) fo(j,1,m) g[i][j] = f[i][j];
        if (flag == 1) {fo(i,1,m) fo(j,1,n) f[i][j] = g[j][i]; swap(n,m);}

        cout<<"YES"<<endl;
        fo(i,1,n) fo(j,1,m) res1[f[i][j]] = i,res2[f[i][j]] = j;
        fo(i,1,n*m) printf("%d %d\n",res1[i],res2[i]);
    }
}

1009 Calabash and Landlord

懒得分类讨论了，直接坐标乘2离散，然后跑dfs

#include<bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
int T,k,i,j,res;
int x[5],y[5],g[10],f[30][30];
void dfs(int x,int y)
{
   if (x < 1 || x > 16 || y < 1 || y > 16) return; 
   if (f[x][y] == 0) f[x][y] = 1; else return;
   dfs(x+1,y); dfs(x-1,y); dfs(x,y+1); dfs(x,y-1);
}
int main()
{
   scanf("%d",&T);
   while (T--)
   {
       scanf("%d%d%d%d",&x[1],&y[1],&x[2],&y[2]);
       scanf("%d%d%d%d",&x[3],&y[3],&x[4],&y[4]);
       k = 0;
       fo(i,1,4) g[++k] = x[i];
       fo(i,1,4) g[++k] = y[i];
       sort(g+1,g+8+1);
       k = unique(g+1,g+8+1) - (g+1);
       fo(i,1,4) x[i] = lower_bound(g+1,g+k+1,x[i]) - g;
       fo(i,1,4) y[i] = lower_bound(g+1,g+k+1,y[i]) - g;
       fo(i,1,4) x[i] *= 2,y[i] *= 2;
       fo(i,1,16) fo(j,1,16) f[i][j] = 0;
       fo(i,x[1],x[2]) f[i][y[1]] = f[i][y[2]] = 1;
       fo(i,y[1],y[2]) f[x[1]][i] = f[x[2]][i] = 1;
       fo(i,x[3],x[4]) f[i][y[3]] = f[i][y[4]] = 1;
       fo(i,y[3],y[4]) f[x[3]][i] = f[x[4]][i] = 1;
       res = 0;
       fo(i,1,16) fo(j,1,16) 
       if (f[i][j] == 0)
       {
           res++; dfs(i,j);
       }
       cout<<res<<endl;
   }
}

1010 Quailty and CCPC

如果金牌最后一名是x.5名，就输出x+1名

#include<bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
struct www{char name[100]; int p,t;} f[100005];
int T,n,d,i,rk;
bool cmp(const www &a,const www &b)
{
    if (a.p != b.p) return a.p > b.p; else return a.t < b.t;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&d);
        fo(i,1,n) scanf("%s%d%d",f[i].name,&f[i].p,&f[i].t);
        if (n * d % 10 != 5) cout<<"Quailty is very great"<<endl; else
        {
            sort(f+1,f+n+1,cmp);
            rk = n * d / 10 + 1;
            printf("%s\n",f[rk].name);
        }
    }
    return 0;
}

1011 Roundgod and Milk Tea

标算是用二分图匹配那套理论，我的贪心也不知道对不对。。
按照1～n的顺序安排班级，当排第i个班级的时候，优先喝第i+1个班级（感觉就是分配某个班级的时候，如果这个班级的奶茶已经被喝掉了就很稳）
如果喝光了就继续喝后面班级的奶茶
然后wa了。。（随便搞一组就被艹掉了）
然后把“要喝的奶茶”从大到小排序就a了（感觉就是尽可能地先多喝奶茶，把大量班级喝光了就比较稳）

#include<bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
struct node{int a,b;} f[1000005];
int T,n,i,r,t,flag;
long long res;
bool cmp(const node &x,const node &y) {if (x.a != y.a) return x.a > y.a; else return x.b < y.b;}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        fo(i,1,n) scanf("%d%d",&f[i].a,&f[i].b);
        sort(f+1,f+n+1,cmp);
        if (n == 1) {cout<<0<<endl; continue;}
        r = 2; res = 0; flag = 0;
        fo(i,1,n)
        {
            if (r == i) {r++; if (r == n + 1) r = 1;}
            t = f[i].a;
            while (1)
            {
                if (f[r].b >= t) {res += t; f[r].b -= t; break;}
                res += f[r].b; t -= f[r].b; f[r].b = 0; r++;
                if (r == n + 1) r = 1;
                if (r == i) {flag++; break;}
            }
            if (flag == 2) break;
        }
        cout<<res<<endl;
    }
    return 0;
}