算法复建第一场www

俺太菜了。思维跟以前比死板了不少。补题补题补题!

Code Jam to I/O for Women 2022题解

Inversions Organize

谁能想到,第一题我就果断WA了一次。

题目大意翻译为:给个n,随即给出2n*2n的字符矩阵,只包含I或O。我们要使用最少的步骤(每次翻转可使I变O,O变I),使左边n列的IO比例与右边n列的IO比例相同,且上边n行的IO比例与下边n行的IO比例相同。题目给出的一个样例如下——

IIOO

OOOI

IIII

OOOI

需要变成

IIOO

OOII

IIII

OOOO

一开始的思路以为每块必须均分IO,直接用n*n与各块现在的I/O数量求abs取最值相加。直接在TEST1 WA掉。后来细细思索了一下,每块不一定全是均等的。因为I和O视作等效的,因此我们先考虑I的情况。将矩阵分为上下左右四等分,每一块I的数量分别为X1,X3,X2,X4。根据题意,有X1+X2=X3+X4;X1+X3=X2+X4。可推出,X1=X4,X2=X3。

也就是满足对角数量相等就可以。只需要统计各块现在的数量,求差。

代码如下:

#include<bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep(x,a,b) for(int x=a;x<b;x++)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

char cc[205][205];

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t,c=1;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=0;i<n*2;i++)
            for(int j=0;j<n*2;j++)
                cin>>cc[i][j];
        int x=0,y=0,xx=0,yy=0,X=0,XX=0,Y=0,YY=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(cc[i][j]=='I') x++;
                else X++;
        for(int i=n;i<n*2;i++)
            for(int j=n;j<n*2;j++)
                if(cc[i][j]=='I') xx++;
                else XX++;
        for(int i=n;i<n*2;i++)
            for(int j=0;j<n;j++)
                if(cc[i][j]=='I') y++;
                else Y++;
        for(int i=0;i<n;i++)
            for(int j=n;j<n*2;j++)
                if(cc[i][j]=='I') yy++;
                else YY++;
        cout<<"Case #"<<c++<<": "<<min(abs(x-xx),abs(X-XX))+min(abs(y-yy),abs(Y-YY))<<endl;
    }
    return 0;
}

Ingredient Optimization

第二题光读题就是读了半天,给出的变量有点多。

有一个罗勒叶中间商,每次需要交付给下面的N个商家U片罗勒叶,同时她有D组收到的罗勒供应。每组罗勒叶有三个参数,M代表生产时间,L代表数量,E代表罗勒叶维持新鲜的时间。需要注意的是,罗勒叶只有在[M,M+E-1]这个时间段交付才有效(M+E这个时间点罗勒叶已经腐败)。保证给出的M严格递增。

同时,N个商家来收货会给出一个时间点O,O也满足严格递增。如果中间商无法给当前的订单供货,则后续订单直接取消。问对于每组给出的数据,最多可以完成多少订单。

数据范围:100组测试,D,N,U,L≤100,M,E,O≤1E9。

首先,可以确定的是,根据题意,总策略一定是贪心的。我们尽可能优先满足当前订单的需求。而我们交付的时候,尽可能先交付即将腐败的罗勒叶(黑心商家orz)。

因为给的是时间区间,我自己在比赛的时候立刻联想到区间操作,单点查询的树状数组。然后开始了漫长的优化操作。

思路偏了,数据范围1E8的话还可以考虑一下,不过属实也是大材小用了,而且对于单点更新区间十分不方便。

看了题解,惊呼妙啊。题解提示可以用最小堆存储罗勒叶,每次交付在最小堆中查询即可。我自己写的时候,直接用了STL的优先队列,底层就是采用堆实现的。按照腐败的时间先后存入优先队列,每次查询取出队首元素,如果符合条件且有剩余,继续放回优先队列,每次查询O(log D),总时间复杂度O( (N+D)log D )。

还有一个细节需要留意。虽然当前罗勒叶不满足商家的时间要求,但是还是有实质不同的。如果在商家时间之前,需要直接丢弃;如果在商家时间之后,是需要保留给下面的商家的。但基于优先队列的结构,不能在这个商家没走之前就放回优先队列,否则会导致死循环,需要先存储起来,等循环结束再依次放回。

代码如下:

#include<bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep(x,a,b) for(int x=a;x<b;x++)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

struct leaf
{
    int b,e,num;
    friend bool operator < (leaf a, leaf b)
    {
        return a.e > b.e;
    }
};

leaf y[105];
priority_queue<leaf>q,qq;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t,cc=1;cin>>t;
    while(t--)
    {
        int d,n,u,ans=0;cin>>d>>n>>u;
        q=qq;
        for(int i=0;i<d;i++)
        {
            int m,l,e;
            cin>>m>>l>>e;
            y[i].b=m;
            y[i].e=m+e-1;
            y[i].num=l;
            q.push(y[i]);
        }
        int f=1;
        for(int i=0;i<n;i++)
        {
            int o,nn=u,ff=0;cin>>o;
            vector<leaf>v;
            while(!q.empty()&&f)
            {
                leaf x=q.top();
                //cout<<x.b<<" "<<x.e<<" "<<x.num<<endl;
                if(x.e<o)
                {
                    q.pop();
                    continue;
                }
                else if(x.b>o)
                {
                    q.pop();
                    v.push_back(x);
                    continue;
                }
                else if(x.num>nn)
                {
                    x.num-=nn;
                    q.pop();
                    q.push(x);
                    ff=1;
                    break;
                }
                else if(x.num==nn)
                {
                    q.pop();
                    ff=1;
                    break;
                }
                else
                {
                    q.pop();
                    nn-=x.num;
                    continue;
                }
            }
            if(!ff) f=0;
            else ans++;
            for(int i=0;i<v.size();i++) q.push(v[i]);
        }
        cout<<"Case #"<<cc++<<": "<<ans<<endl;
    }
    return 0;
}

小蠢货