World Finals 2017 (水题题解)

看大佬做2017-WF，我这种菜鸡，只能刷刷水题，勉强维持生活。 赛后补补水题。

题目pdf链接，中文的，tls翻译的，链接在这里

个人喜欢在vjudge上面刷题。

题意：

思路：

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <string.h>

using namespace std;

typedef long long int LL;

const int INF=2e9+1e8;

const int maxn=1e6+100;

const double eps=1e-8;

int di[maxn],si[maxn],n,T;

bool judge(double mid)

{

    double ans=0;

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

    {

        ans+=di[i]/(si[i]+mid);

    }

   // printf("mid=%lf ans=%lf\n",mid,ans);

    return ans>=T;

}

double solve(double l,double r)

{

    double ans=-100000;

    while((l<=r)&&(r-l>eps))

    {

        double mid=(l+r)/2;

        //printf("l=%")

        //  printf("mid=%lf flag=%d\n",mid,judge(mid));

        if(judge(mid)) l=mid;

        else r=mid;

        ans=mid;

    }

    return ans;

}

//#define JJ -0.508653377

int main()

{

    // printf("%lf\n",5/(3+JJ)+2/(2+JJ)+3/(6+JJ)+3/(1+JJ));

    scanf("%d%d",&n,&T);

    int l=INF;

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

    {

        scanf("%d%d",&di[i],&si[i]);

        l=min(si[i],l);

    }

    printf("%lf\n",solve(double(-l),100000000.));

    return 0;

}

Problem I ：Secret Chamber at Mount Rushmore

题目描述：

题目思路：

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <string.h>

#include <string>

#include <queue>

using namespace std;

typedef long long int LL;

const int INF=2e9+1e8;

const int maxn=1e6+100;

const double eps=1e-8;

struct Node

{

	char t;

	int next;

}edge[maxn];

int first[265],sz;

void init()

{

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

	sz=0;

}

void addedge(char s,char t)

{

	edge[sz].t=t,edge[sz].next=first[(int)s];

	first[(int)s]=sz++;

}

bool maze[265][265];

bool vis[264];

void dfs(int now,int to)

{

	maze[now][to]=1;

	vis[to]=1;

	for(int i=first[to];i!=-1;i=edge[i].next)

	{

		int t=edge[i].t;

		if(vis[t]==0) dfs(now,t);

	}

}

int main()

{

	init();

	int n,m;

	scanf("%d%d",&n,&m);

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

	{

		char s[5],t[5];

		scanf("%s%s",s,t);

		addedge(s[0],t[0]);

	}

	memset(maze,0,sizeof(maze));

	for(char i='a';i<='z';i++)

	{

		memset(vis,0,sizeof(vis));

		dfs(i,i);

	}

	while(m--)

	{

		char a[100],b[100];

		int lena,lenb;

		scanf("%s%s",a,b);

		lena=strlen(a),lenb=strlen(b);

		if(lena!=lenb) printf("no\n");

		else

		{

			bool flag=true;

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

			{

				if(maze[(int)a[i]][(int)b[i]]==0)

				{

					flag=false;

					break;

				}

			}

			if(flag) printf("yes\n");

			else printf("no\n");

		}

	}

	return 0;

}

题目链接：C - Mission Improbable

题目意思：

解题思路：

弱弱代码，仅供参考。

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <time.h>

using namespace std;

typedef long long LL;

const int INF = 2e9 + 1e8;

const int MOD = 1e9 + 7;

const double eps = 0.0000000001;

void fre()

{

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

}

#define MSET(a, b) memset(a, b, sizeof(a))

#define fr(i, a, n) for (int i = a; i < n; i++)

const int maxn = 150;

int mat[maxn][maxn];

int side[maxn], front[maxn];

int G[maxn][maxn];

int vis[maxn], link[maxn], n, m;

int match(int x)

{

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

    {

        if (!vis[i] && G[x][i])

        {

            vis[i] = 1;

            if (!link[i] || match(link[i]))

            {

                link[i] = x;

                return 1;

            }

        }

    }

    return 0;

}

int main()

{

    scanf("%d%d", &n, &m);

    LL sum = 0, sub = 0;

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

    {

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

        {

            scanf("%d", &mat[i][j]);

            side[i] = max(side[i], mat[i][j]);

            front[j] = max(front[j], mat[i][j]);

            if (mat[i][j])

                sub++;

            sum += mat[i][j];

        }

    }

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

    {

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

        {

            if (mat[i][j] && side[i] == front[j])

                G[i][j] = 1;

        }

    }

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

    {

        memset(vis, 0, sizeof(vis));

        match(i);

    }//匹配

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

        if (side[i])

            sub += side[i] - 1; //统计侧视图

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

        if (!link[i] && front[i])

            sub += front[i] - 1; //把没匹配的额外加；

    printf("%lld\n", sum - sub);

    return 0;

}

--------- D - Money for Nothing -------------

题目描述：

解题思路：

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <string>

using namespace std;

typedef long long int LL;

#define MSET(a,b) memset(a,b,sizeof(a))

const int maxn=1e6+10;

struct Point

{

    int x,y;

}A[maxn],B[maxn],T[maxn];

bool cmp(Point a,Point b) //x递增，y递增

{

    if(a.x!=b.x) return a.x <b.x;

    return a.y<b.y;

}

LL ans;

int dp[maxn];

void dfs(int l,int r,int L,int R)

{

    if(l>r||A[r].y>=B[L].y||A[l].x>=B[R].x) return ;

    int mid=(l+r)>>1,pos=0;

    int s=lower_bound(dp+L,dp+R+1,A[mid].x)-dp;

    LL mx=0;

    for(int i=s;i<=R;i++)

    {

        if(B[i].y<=A[mid].y) break;

        LL val=1ll*(B[i].y-A[mid].y)*(B[i].x-A[mid].x);

        if(val>mx) mx=val,pos=i;

        //if(val>ans) ans=val,pos=i;

    }

    ans=max(ans,mx);

    if(pos) dfs(l,mid-1,L,pos),dfs(mid+1,r,pos,R);

    else dfs(l,mid-1,L,R),dfs(mid+1,r,L,R);

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)+1)

    {

        for(int i=1;i<=n;i++) scanf("%d%d",&A[i].x,&A[i].y);

        for(int i=1;i<=m;i++) scanf("%d%d",&T[i].x,&T[i].y);

        sort(A+1,A+1+n,cmp);

        sort(T+1,T+1+m,cmp);

        int ia=1,ib=1;

        A[1]=A[1],B[1]=T[m];

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

            if(A[i].y<A[ia].y) A[++ia]=A[i];

        for(int i=m-1;i>0;i--)

            if(T[i].y>B[ib].y) B[++ib]=T[i];

        reverse(B+1,B+1+ib);

        for(int i=1;i<=ib;i++) dp[i]=B[i].x;

        // for(int i=1;i<=ia;i++)

        //     printf(">>> %d %d\n",A[i].x,A[i].y);

        // for(int i=1;i<=ib;i++)

        //     printf(">>> %d %d\n",B[i].x,B[i].y);

        ans=0;

        dfs(1,ia,1,ib);

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

    }

    return 0;

}

--------- F - Posterize -------------

题目描述：

解题思路：

code :

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <time.h>

using namespace std;

typedef long long LL;

const int INF = 2e9 + 1e8;

const int MOD = 1e9 + 7;

const double eps = 0.0000000001;

void fre()

{

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

}

#define MSET(a, b) memset(a, b, sizeof(a))

#define fr(i, a, n) for (int i = a; i < n; i++)

const int maxn = 300;

LL fx[maxn][maxn], dp[maxn][maxn];

int red[maxn];

void Min(LL &x, LL t)

{

    if (t < x)

        x = t;

}

int main()

{

    int n, k;

    scanf("%d%d", &n, &k);

    MSET(dp, 0x7f);

    MSET(fx, 0x7f);

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

    {

        int r, p;

        scanf("%d%d", &r, &p);

        red[r] = p;

    }

    for (int color = 0; color <= 255; color++)

    {

        for (int l = 0; l <= 255; l++)

        {

            LL num = 0;

            for (int r = l; r <= 255; r++)

            {

                num += 1ll * (r - color) * (r - color) * red[r];

                Min(fx[l][r], num);

            }

        }

    }

    //处理出，f[l][r];代表区间 l，r；

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

        dp[i][1] = fx[0][i];

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

        for (int j = 2; j <= k; j++)

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

                Min(dp[i][j], dp[t][j - 1] + fx[t + 1][i]);

    cout << dp[255][k] << endl;

    return 0;

}