2019 Multi-University Training Contest 9

1002 Rikka with Cake

题目链接
题意：给你一个n*m的蛋糕，在蛋糕上有许多点，然后根据点和方向切，求最后能切多少块蛋糕。
思路：将每个点排序，离散化x轴建线段树。我们把竖着切和横着切看作两种操作。竖着切就是对于此下标，单点更新，横着切可以看作下标到两端的某一段的区间求和。向上切和向下切两个方向分开讨论，跑两遍线段树。最后答案加上1，即原有的那个蛋糕。

正解：通过几何学中的欧拉公式
其中V代表顶点个数，E代表边数，F代表块数。计算可得最后答案就是交点数C+1。用线段树或树状数组求交点。

图片说明 

#include <bits/stdc++.h>

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

int n,m,k;
// f 1 2 3 4  上 右 下 左 
struct line{
    int x,y,f;
}li[maxn];
int xCopy[maxn];
int size;

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

    sort(xCopy,xCopy+k);
    size=unique(xCopy,xCopy+k)-xCopy;
}

int Hash(int x){
    return lower_bound(xCopy,xCopy+size,x)-xCopy+1;
}

bool cmp1(line a,line b){
    return a.y<b.y;
}

bool cmp2(line a,line b){
    return a.y>b.y;
}


void input(){
    scanf("%d%d%d",&n,&m,&k);
    int i;
    char s[3];
    for(i=0;i<k;i++){
        scanf("%d%d%s",&li[i].x,&li[i].y,s);
        if(s[0]=='U')
            li[i].f=1;
        else if(s[0]=='R')
            li[i].f=2;
        else if(s[0]=='D')
            li[i].f=3;
        else if(s[0]=='L')
            li[i].f=4;
    }

    Init_Hash_x();
    sort(li,li+k,cmp1);
}

struct LR_sum_SEG {
    ll val[maxn << 2];
    void pushup(int p) {
        val[p] = val[p << 1 | 1]+val[p << 1];
    }

    void build(int p, int l, int r) {
        if (l == r) {
            val[p] = 0;
            return;
        }
        int mid = l + r >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        pushup(p);
    }

    void update(int p, int l, int r, int index, int x) {
        if(l==r){
            val[p]+=x;
            return;
        }

        int mid = l + r >> 1;
        if(index<=mid) update(p<<1,l,mid,index,x);
        else update(p<<1|1,mid+1,r,index,x);
        pushup(p);
    }

    int query(int p, int l, int r, int L,int R) {
        if(L<=l&&r<=R){
            return val[p];
        }

        int mid = l + r >> 1;
        int ans=0;
        if(L<=mid) ans+=query(p<<1,l,mid,L,R);
        if(R>mid) ans+=query(p<<1|1,mid+1,r,L,R);
        return ans;
    }
}SEG;

void solve(){
    ll ans=1;

    int i;
    SEG.build(1,1,100002);
    for(i=0;i<k;i++){
        if(li[i].f==1){
            SEG.update(1,1,100002,Hash(li[i].x)+1,1);
        }else if(li[i].f==2){
            ans+=SEG.query(1,1,100002,Hash(li[i].x)+1,100002);
        }else if(li[i].f==4){
            ans+=SEG.query(1,1,100002,1,Hash(li[i].x)+1);
        }
    }

    sort(li,li+k,cmp2);
    SEG.build(1,1,100002);
    for(i=0;i<k;i++){
        if(li[i].f==3){
            SEG.update(1,1,100002,Hash(li[i].x)+1,1);
        }else if(li[i].f==2){
            ans+=SEG.query(1,1,100002,Hash(li[i].x)+1,100002);
        }else if(li[i].f==4){
            ans+=SEG.query(1,1,100002,1,Hash(li[i].x)+1);
        }
    }

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

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

1005 Rikka with Game

题目链接
题意：一个全是小写字母的字符串，A、B两个人都可以轮流选择其中一个字母，使其+1。（即a->b,b->c....y->z,z->a）或者可以立刻结束游戏。先手的人希望将字符串字典序小，后手的人希望字典序尽量大。求最后的答案。
思路：1、当第一个字母是a-x中其中一个时，先手会直接结束游戏。若先手选择第一个字母+1，后手可以选择继续增加或者终止游戏，字典序一定会增加。
2、当第一个字母为y时，先手、后手都不会动这一位。若先手增加，后手可以终止在z上，字典序增加。若后手增加，先手可以继续增加，使其变为a。增加y都是亏的。
3、当第一个字母为z时，先手必然增加为a。回到第一种情况

结论就是，找到第一位不是y的位，如果它是z，则修改成b，否则不变

#include <bits/stdc++.h>

using namespace std;

string s;
void input(){
    cin>>s;
}

void solve(){
    for(int i=0;i<s.size();i++){
        if(s[i]=='y')
            continue;
        else if(s[i]=='z')
        {
            s[i]='b';
            break;
        }else
            break;
    } 
    cout<<s<<endl;
}

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

1006 Rikka with Coin

题目链接
题意：有无数个10、20、50、100的硬币，有n个物品其价格为wi，求找到最少的硬币数，满足能凑整所有的wi，若不能输出-1
思路：对于10的硬币，使用的次数在[0,1]之间，当我们选择两个10硬币，可以选择一个10、一个20的硬币更优。
对于20的硬币，使用次数在[0,3]之间，当我们选择四个20硬币，可以选择一个10、一个20、一个50的硬币更优。
对于50的硬币，使用次数在[0,1]之间，当我们选择两个50硬币，可以选择一个50、一个100的硬币更优。

故我们可以枚举这些硬币出现次数，然后多余的用100补。取多种解法中最小答案。

#include <bits/stdc++.h>

#define maxn 105
#define inf 0x3f3f3f3f
using namespace std;

int n;
int w[maxn];
int l;
void input(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&w[i]);
}

bool check(int x,int y,int z){
    vector <int>v;
    int i,j,k;
    for(i=0;i<=x;i++)
        for(j=0;j<=y;j++)
            for(k=0;k<=z;k++)
                v.push_back(10*i+j*20+k*50);

    l=0;
    for(i=0;i<n;i++){
        int flag=1;
        int temp=inf;
        for(j=0;j<v.size();j++){
            if(w[i]-v[j]>=0&&(w[i]-v[j])%100==0)
                temp=min(temp,(w[i]-v[j])/100);
        }
        if(temp==inf)
            return 0;
//        cout<<l<<" "<<temp<<endl;
        l=max(l,temp);    
    }
    return 1;
}

void solve(){
    int i,j,k;
    int ans=inf;
    for(i=0;i<2;i++){
        for(j=0;j<4;j++){
            for(k=0;k<2;k++){
                if(check(i,j,k)){
//                    cout<<i<<' '<<j<<' '<<k<<' '<<l<<endl;
                    ans=min(ans,i+j+k+l);
                }
            }
        }
    }
    if(ans==inf)
        printf("-1\n");
    else
        printf("%d\n",ans);
}

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

/*
1
4
110 160 190 410
*/

1007 Rikka with Travels

题目链接
题意：给你一个n个节点的树，在上面寻找到两条互不重叠的路径。要求以两条路径长度作为值，寻找至多的二元组(L1,L2)数量。
思路：首先我们在树上找到最长的两条互不重叠的路径，其小于它们的路径也包含在了其中。可以证明要寻找最长的两条路径，直径的两个端点一定包含在这些路径中。

图片说明

求出原树的直径。将直径上的边都拆去。再跑直径上所有点的DFS，可知以直径上点为端点的最长扩展子路径len[i]。

当两个端点分别包含在两个路径中时，O(n)枚举一个端点到直径上某个点作为扩展路径点，即dis[i]+len[i]。另一个端点到这个点之间的最长路径可以记录max扩展maxx[i]和dis[i]得到。
当两个端点包含在同一个路径中时，可以将所有和直径点相连的端点再拆去。在所有子图上都跑DFS找最长直径。

得到的两两一组的最大路径长度后，O(n)更新。链式前向星建图。

#include <bits/stdc++.h>

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

int n,m;
struct edge{
    int to,next;
    int book;
}G[maxn<<1];
int head[maxn];
int edgeNum=0;

int S,T,now;
int Fa[maxn];
int pre[maxn];
int book[maxn];
int dis[maxn];
int vis[maxn];
int len[maxn];
int val[maxn];
int maxx[maxn];

void add_edge(int a,int b)//添加单向边 类似链表存储 head[i]代表链表头 例如n=1e6 m<=2*n时不能通过邻接表存储
{
    G[edgeNum].to=b;
    G[edgeNum].next=head[a];
    head[a]=edgeNum++;
}

void dfs(int fa,int x,int step){

    int i;
    if(step>now){
        now=step;
        S=x;
    }

    for(i=head[x];i!=-1;i=G[i].next)
    {
        if(G[i].to==fa||G[i].book)continue;
        else dfs(x,G[i].to,step+1);
    }        
}

void dfs2(int fa,int x,int step){
    int i;
    Fa[x]=fa;
    dis[x]=step;
    if(step>now){
        now=step;
        T=x;
    }

    for(i=head[x];i!=-1;i=G[i].next)
    {
        if(G[i].to==fa||G[i].book)continue;
        else dfs2(x,G[i].to,step+1);
    }
}

void dfs3(int fa,int x,int step){
    int i;
    vis[x]=1;
    if(step>now)
        now=step;

    for(i=head[x];i!=-1;i=G[i].next)
    {
        if(G[i].to==fa||G[i].book||vis[G[i].to])continue;
        else dfs3(x,G[i].to,step+1);
    }
}

void input(){
    scanf("%d",&n);
    edgeNum=0;

    memset(vis,0,sizeof vis);
    for(int i=0;i<maxn<<1;i++)
        G[i].book=0;

    for(int i=0;i<maxn;i++){
        book[i]=0;
        val[i]=0;
        head[i]=-1;
    }

    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
}

void solve(){
    now=-1;
    dfs(-1,1,0);
    now=-1;
    dfs2(-1,S,0);
    int i,j;
    for(i=T;i!=-1;i=Fa[i]){
        book[i]=1;
        vis[i]=1;
    }

    for(i=T;i!=-1;i=Fa[i])
        for(j=head[i];j!=-1;j=G[j].next)
            if(book[G[j].to])
                G[j].book=1;

    int original=S;
    int lst;
    for(i=T;i!=-1;i=Fa[i]){
        now=-1;
        dfs(-1,i,0);
        len[i]=now;

        if(i==T){
            pre[i]=-1;
            lst=i;
        }else{
            pre[i]=lst;
            lst=i;
        }

//        cout<<"len:"<<i<<" "<<len[i]<<endl;
    }

    for(i=S;i!=-1;i=pre[i]){
        if(i==S){
            maxx[i]=len[i];
        }else{
            maxx[i]=max(maxx[Fa[i]],dis[i]+len[i]+1);
        }
    }

    S=original;
//    cout<<"T:"<<T<<' '<<"S:"<<S<<endl;
    int temp;
    for(i=T;i!=-1;i=Fa[i]){
//        cout<<"!"<<i<<endl;
        if(i==T){
            temp=i;
        }else{
            int len1=dis[T]-dis[i]+len[i]+1;
            int len2=maxx[Fa[i]];
//            cout<<"!"<<len1<<" "<<len2<<endl;

            val[len1]=max(val[len1],len2);
            val[len2]=max(val[len2],len1);
        }
    }

    for(i=T;i!=-1;i=Fa[i])
        for(j=head[i];j!=-1;j=G[j].next)
            G[j].book=1;

    for(i=0;i<edgeNum;i++)
        if(book[G[i].to])
            G[i].book=1;

    int L=0;
    int final=T;
    for(i=1;i<=n;i++)
    {
        if(!vis[i]){
//            cout<<i<<endl;
            now=-1;
            dfs(-1,i,0);
            now=-1;
            dfs3(-1,S,0);
            L=max(L,now);
        }
    }
    dis[final]++;
    if(n!=dis[final])
        L++;
//    cout<<"!"<<L<<' '<<dis[final]<<endl;

    val[dis[final]]=max(val[dis[final]],L);
    val[L]=max(val[L],dis[final]);

    ll sum=0;
    for(int i=n;i>=1;i--){
        if(val[i]<val[i+1])
            val[i]=val[i+1];
        sum+=val[i];
    }

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

int main(){
//    freopen("in","r",stdin);
//    freopen("out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();
    }    
}

1008 Rikka with Stable Marriage

题目链接
题意：给你a数组和b数组要求其两两异或，得到最后和最大。
思路：杭电多校第五场，有道类似的题，求最后数值字典序最小。那道正解用栈和字典树维护，可以用两个指针在两个字典树上跑，贪心求最后答案。这题类似。建立两个字典树，用两个指针在字典树上跑，记录每个结点出现次数。贪心思路，若两个指针能够不同就先不同，否则就相同。

#include <bits/stdc++.h>

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

int n;
int tol[2]={1,1};
int t[2][31*maxn][2];
int val[2][31*maxn];
int ans[maxn];
int a[maxn];
int b[maxn];

void insert(int x,int flag){
    int u=0;
    for(int i=30;i>=0;i--){
        int v=(x>>i)&1;
        if(!t[flag][u][v]){
            t[flag][u][v]=tol[flag]++;
        }
        u=t[flag][u][v];
        val[flag][u]++;
    }
}

int query(){
    int p0=0;
    int p1=0;
    int x=0;
    for(int i=30;i>=0;i--){
        if(val[0][t[0][p0][0]]&&val[1][t[1][p1][1]]){
            p0=t[0][p0][0];
            val[0][p0]--;
            p1=t[1][p1][1];
            val[1][p1]--;
            x+=(1<<i);
        }else if(val[0][t[0][p0][1]]&&val[1][t[1][p1][0]]){
            p0=t[0][p0][1];
            val[0][p0]--;
            p1=t[1][p1][0];
            val[1][p1]--;
            x+=(1<<i);
        }else if(val[0][t[0][p0][0]]&&val[1][t[1][p1][0]]){
            p0=t[0][p0][0];
            val[0][p0]--;
            p1=t[1][p1][0];
            val[1][p1]--;
        }else{
            p0=t[0][p0][1];
            val[0][p0]--;
            p1=t[1][p1][1];
            val[1][p1]--;
        }
    }
    return x;
}

void input(){
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        insert(a[i],0);
    }

    for(i=1;i<=n;i++){
        scanf("%d",&b[i]);
        insert(b[i],1);
    }    
}

void solve(){
    int i;
    ll sum=0;
    for(i=1;i<=n;i++){
        ans[i]=query();
//        cout<<ans[i]<<endl;
        sum+=ans[i];
    }

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

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        tol[0]=tol[1]=1;
        memset(val,0,sizeof val);
        memset(t,0,sizeof t);
        input();
        solve();
    }
}