Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)

2016年11月10日5,2980

A. Checking the Calendar

问有没有可能存在一年中的连续两个月，第一个月的第一天的星期是给定的第一个字符串，第二个月的第一天的星期是给定的第二个字符串

模拟即可

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int t[12]={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
string d[7]={"monday", "tuesday", "wednesday", "thursday", "friday", "saturday", "sunday"};
string s1,s2;
int num(string a)
{
    for(int i=0;i<7;i++)
        if(a==d[i])return i;
}
int main()
{
    cin>>s1>>s2;
    for(int i=0;i<11;i++)
        if((num(s2)-num(s1)+7)%7==t[i]%7)
        {
            puts("YES");
            return 0;
        }
    puts("NO");
    return 0;
}

#include<map>

#include<set>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int t[12]={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

string d[7]={"monday", "tuesday", "wednesday", "thursday", "friday", "saturday", "sunday"};

string s1,s2;

int num(string a)

{

for(int i=0;i<7;i++)

if(a==d[i])return i;

}

int main()

{

cin>>s1>>s2;

for(int i=0;i<11;i++)

if((num(s2)-num(s1)+7)%7==t[i]%7)

{

puts("YES");

return 0;

}

puts("NO");

return 0;

}

B. Batch Sort

给你n行，每行都是一个1-m的排列。

\(1\leq n\leq 20,1\leq m\leq 20\)

你可以交换任意两列，并且你可以每行最多交换两个元素，问你能不能使得每行都是单增的

枚举两列交换，每行贪心

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[25][25];
void swapc(int x,int y)
{
    for(int i=1;i<=n;i++)
        swap(a[i][x],a[i][y]);
}
bool check()
{
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<=m;j++)
            if(a[i][j]!=j)cnt++;
        if(cnt>2)return 0;
    }
    return 1;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=read();
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
        {
            swapc(i,j);
            if(check())
            {
                puts("YES");
                return 0;
            }
            swapc(i,j);
        }
    puts("NO");
    return 0;
}

#include<map>

#include<set>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int a[25][25];

void swapc(int x,int y)

{

for(int i=1;i<=n;i++)

swap(a[i][x],a[i][y]);

}

bool check()

{

for(int i=1;i<=n;i++)

{

int cnt=0;

for(int j=1;j<=m;j++)

if(a[i][j]!=j)cnt++;

if(cnt>2)return 0;

}

return 1;

}

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

a[i][j]=read();

for(int i=1;i<=m;i++)

for(int j=i;j<=m;j++)

{

swapc(i,j);

if(check())

{

puts("YES");

return 0;

}

swapc(i,j);

}

puts("NO");

return 0;

}

C. Ray Tracing

从(0,0)向(1,1)发射光线，在一个\(n*m\)的矩形里面不断反射

然后k个询问，问你第一次到某个点的时间

\(1\leq n,m,K\leq 10^5\)

其实可以用数论求解QAQ

考虑经过某个点的光线为\(y=x+b\)或\(y=-x+b\)

比较难写的模拟。。。用两个set维护所有的点，每次删去一条光线上经过的点，并计算反射后的光线

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mp(x,y) make_pair(x,y)
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int x,y,K;
set<pair<int,int> >st1,st2;
ll ans[100005],a[100005],b[100005];
set<pair<int,int> >::iterator it;
bool check(int a,int b)
{
    if(a==x&&b==y)return 1;
    if(a==0&&b==y)return 1;
    if(a==x&&b==0)return 1;
    return 0;
}
void solve()
{
    int nx=0,ny=0,dir=1,tmp;
    ll tot=0;
    while(1)
    {
        int now=nx-ny;
        it=st1.lower_bound(mp(now,0));
        while(it!=st1.end()&&it->first==now)
        {
            int t=(*it).second;
            if(ans[t]==-1)ans[t]=abs(a[t]-nx)+tot;
            st1.erase(it);
            it=st1.lower_bound(mp(now,0));
        }
        if(dir==1)tmp=min(x-nx,y-ny);
        else tmp=min(nx,ny);
        nx+=tmp*dir;ny+=tmp*dir;tot+=tmp;
        if(ny==y||nx==0)dir=-1;
        else dir=1;
        
        if(check(nx,ny))return;

        
        now=nx+ny;
        it=st2.lower_bound(mp(now,0));
        while(it!=st2.end()&&it->first==now)
        {
            int t=(*it).second;
            if(ans[t]==-1)ans[t]=abs(a[t]-nx)+tot;
            st2.erase(it);
            it=st2.lower_bound(mp(now,0));
        }
        if(dir==1)tmp=min(nx,y-ny);
        else tmp=min(x-nx,ny);
        nx-=tmp*dir;ny+=tmp*dir;tot+=tmp;
        if(check(nx,ny))return;
        
        if(ny==0||nx==0)dir=1;
        else dir=-1;
    }
}
int main()
{
    x=read();y=read();K=read();
    for(int i=1;i<=K;i++)
    {
        a[i]=read(),b[i]=read();
        st1.insert(mp(a[i]-b[i],i));
        st2.insert(mp(a[i]+b[i],i));
    }
    memset(ans,-1,sizeof(ans));
    solve();
    for(int i=1;i<=K;i++)
        cout<<ans[i]<<endl;
    return 0;
}

#include<map>

#include<set>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mp(x,y) make_pair(x,y)

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int x,y,K;

set<pair<int,int> >st1,st2;

ll ans[100005],a[100005],b[100005];

set<pair<int,int> >::iterator it;

bool check(int a,int b)

{

if(a==x&&b==y)return 1;

if(a==0&&b==y)return 1;

if(a==x&&b==0)return 1;

return 0;

}

void solve()

{

int nx=0,ny=0,dir=1,tmp;

ll tot=0;

while(1)

{

int now=nx-ny;

it=st1.lower_bound(mp(now,0));

while(it!=st1.end()&&it->first==now)

{

int t=(*it).second;

if(ans[t]==-1)ans[t]=abs(a[t]-nx)+tot;

st1.erase(it);

it=st1.lower_bound(mp(now,0));

}

if(dir==1)tmp=min(x-nx,y-ny);

else tmp=min(nx,ny);

nx+=tmp*dir;ny+=tmp*dir;tot+=tmp;

if(ny==y||nx==0)dir=-1;

else dir=1;

if(check(nx,ny))return;

now=nx+ny;

it=st2.lower_bound(mp(now,0));

while(it!=st2.end()&&it->first==now)

{

int t=(*it).second;

if(ans[t]==-1)ans[t]=abs(a[t]-nx)+tot;

st2.erase(it);

it=st2.lower_bound(mp(now,0));

}

if(dir==1)tmp=min(nx,y-ny);

else tmp=min(x-nx,ny);

nx-=tmp*dir;ny+=tmp*dir;tot+=tmp;

if(check(nx,ny))return;

if(ny==0||nx==0)dir=1;

else dir=-1;

}

int main()

{

x=read();y=read();K=read();

for(int i=1;i<=K;i++)

{

a[i]=read(),b[i]=read();

st1.insert(mp(a[i]-b[i],i));

st2.insert(mp(a[i]+b[i],i));

}

memset(ans,-1,sizeof(ans));

solve();

for(int i=1;i<=K;i++)

cout<<ans[i]<<endl;

return 0;

}

D. Dense Subsequence

给一个字符串，从中选出一串字符，使得这串字符的排序后字典序最小

若上一次选第i个字符，\([i+1,i+m]\)中至少选一个

贪心，枚举选到某一个字母x，比x的全都选，然后选尽量少的x

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mp(x,y) make_pair(x,y)
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
string s;
int a[100005];
bool mark[100005];
vector<int> ans;
bool solve(int x)
{
    ans.clear();
    int l=1,r=m,last=-1;
    while(r<n)
    {
        if(a[l]<x)last=-1,r=l+m;
        if(a[l]==x)last=l;
        if(l==r)
        {
            if(last==-1)return 0;
            r=last+m;ans.push_back(x);
        }
        l++;if(l>r)return 0;
    }
    return 1;        
}
int main()
{
    m=read();
    cin>>s;n=s.length();
    if(m>=n)
    {
        sort(s.begin(),s.end());
        cout<<s[0]<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++)
        a[i]=s[i-1]-'a'+1;
    for(int i=1;i<=26;i++)
        if(solve(i))
        {
            for(int j=1;j<=n;j++)
                if(a[j]<i)ans.push_back(a[j]);
            sort(ans.begin(),ans.end());
            for(int j=0;j<ans.size();j++)
                cout<<char(ans[j]+'a'-1);
            cout<<endl;
            return 0;
        }
    return 0;
}

#include<map>

#include<set>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mp(x,y) make_pair(x,y)

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

string s;

int a[100005];

bool mark[100005];

vector<int> ans;

bool solve(int x)

{

ans.clear();

int l=1,r=m,last=-1;

while(r<n)

{

if(a[l]<x)last=-1,r=l+m;

if(a[l]==x)last=l;

if(l==r)

{

if(last==-1)return 0;

r=last+m;ans.push_back(x);

}

l++;if(l>r)return 0;

}

return 1;

}

int main()

{

m=read();

cin>>s;n=s.length();

if(m>=n)

{

sort(s.begin(),s.end());

cout<<s[0]<<endl;

return 0;

}

for(int i=1;i<=n;i++)

a[i]=s[i-1]-'a'+1;

for(int i=1;i<=26;i++)

if(solve(i))

{

for(int j=1;j<=n;j++)

if(a[j]<i)ans.push_back(a[j]);

sort(ans.begin(),ans.end());

for(int j=0;j<ans.size();j++)

cout<<char(ans[j]+'a'-1);

cout<<endl;

return 0;

}

return 0;

}

E. Goods transportation

给n个城市，每个城市可以往比它编号大的城市运输c的货物，每个城市有\(p_i\)的货物，最多消耗\(s_i\)的货物

问最多消耗多少货物

\(1\leq n\leq 10000\)

依据题意可以建立网络流模型，然而图太大无法套用网络流算法

考虑S到T的最小割，用\(F(i,j)\)表示前i个结点，有j个结点属于T集的最小割，考虑第i个结点是否属于T集

那么\(F(i,j)=min(F(i-1,j)+p_i+j*c,F(i-1,j-1)+s_i)\)

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;ll C;
ll p[10005],s[10005];
ll f[2][10005];
int main()
{
    memset(f,127,sizeof(f));
    n=read();C=read();
    for(int i=1;i<=n;i++)p[i]=read();
    for(int i=1;i<=n;i++)s[i]=read();
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            f[i&1][j]=f[(i-1)&1][j]+p[i]+j*C;
            if(j)f[i&1][j]=min(f[i&1][j],f[(i-1)&1][j-1]+s[i]);
        }
    }
    ll ans=f[n&1][0];
    for(int i=1;i<=n;i++)
        ans=min(ans,f[n&1][i]);
    cout<<ans<<endl;
    return 0;
}

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;ll C;

ll p[10005],s[10005];

ll f[2][10005];

int main()

{

memset(f,127,sizeof(f));

n=read();C=read();

for(int i=1;i<=n;i++)p[i]=read();

for(int i=1;i<=n;i++)s[i]=read();

f[0][0]=0;

for(int i=1;i<=n;i++)

{

for(int j=0;j<=i;j++)

{

f[i&1][j]=f[(i-1)&1][j]+p[i]+j*C;

if(j)f[i&1][j]=min(f[i&1][j],f[(i-1)&1][j-1]+s[i]);

}

ll ans=f[n&1][0];

for(int i=1;i<=n;i++)

ans=min(ans,f[n&1][i]);

cout<<ans<<endl;

return 0;

}

« 2016 ACM – ICPC Shenyang Onsite 2015 ACM / ICPC EC – Final »

hzwer.com _ Home | http://hzwer.com

Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)

分类目录

热门文章

Myfriends

近期评论