World Finals 2017 (水题题解)

时间：2023-03-10 01:05:43
World Finals 2017 (水题题解)

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

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

个人喜欢在vjudge上面刷题。

E Need for Speed

题意：

有中文题意，我就不多说了，仪表盘会有一个固定偏差，求这个。

思路：

二分答案，进行判断，二分的上下限，我是 -1 到 1e8；一开始范围错了WA掉了。

#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

题目描述：

有一组转化关系，如果字符 a->b, b->c, 那么 a->c 也成立。问，给定一些关系，前面的字符串能否转为后面的字符串？ yes：no

题目思路：

一开始预处理出，任意两点是否能到达。枚举每一个起点进行dfs。后面\(O(1)\)查询。

#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

题目意思：

给你一个平面图代表每一个位置的箱子个数，问做多拿走多少个箱子，三视图不变？

解题思路：

看了题解慢慢懂的，问题在于求哪些箱子需要保留下来。才能保证三视图不变。首先我们想俯视图，只需要让有的地方留一个箱子即可。其次，正视图，侧视图。我们可以这样子思考，先不管正视图。我侧视图，选完了再说。那么侧视图需要保留的个数就是每行的最大值减一。

那么现在来考虑正视图。正视图应该如何选择才能使得选择最少并且满足条件？ 如果侧视图选中了正视图的最大值那么正视图就不需要额外再选择。刚好，二分图匹配能解决，我们让二分图左边是行号，右边是列号。当某个位置既是行的最大值又是列的最大值，那么我们就在i行与j列之间建一条边。跑一遍匈牙利算法之后，匹配是最大的，意思就是让尽可能多的行列公用一个元素，之后对于无法公用的列那就让该列选择该列的最大值即可。

弱弱代码，仅供参考。

#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 -------------

题目描述：

2017 World Final D,原本的题意就不说，我转化一下就是。给定两个点的集合set:\(A\);set:\(B\),任意在两个集合中各选一个，求最大的 \(max\left ( \left ( x_B - x_A \right )\times \left ( y_B-y_A \right ) \right )\);再和0取一下最大值（即为：最大值为负数输出0）。

解题思路：

参见了大佬的解法，可以把A集合的点和B集合的点都描在二维坐标系中。我们可以很容易发现，A集合中x相同的尽量取y小的，B集合中x相同的尽量取y较大的。那么我们可以将集合A按照 x的递增且y的递增 进行排序。那么我们从前往后遍历y只有变小才有可能比前一个的答案更优。否则就没意义，不保留那个元素。

对于集合B来讲，我们也对B集合按照A集合的方式进行排序。因为我们需要尽量y大的数，我们可以从后往前遍历，只有y变大了才可能更优；处理完后我们得到的A，B集合都是x严格递增y严格递减的序列；

根据官方题解：

假设P代表一个点，\(i < j\),\(P_i , P_j\)是A集合的点，\(k < l\),\(P_k , P_l\)是B集合的元素，我们定义\(f\left ( x,y\right )\)代表y点为右上角，x为左下角这个对角线所构成的矩形面积。画图可验证一个结论:

\(f\left ( i,k\right )+f\left ( j,l \right )\geq f\left ( i,l\right )+f\left ( j,k \right )\)

这个结论告诉我们，A集合中每个点的最优的与B的连线不会有相交除了端点处。有了这个结论分治法就可以解。

不知道如何分治，看这里。分治，快排算法类似的，选A集合中间的位置，找到A的最优解位置，以这个位置将原来的集合分为两个。再解决。具体看代码一目连然。

#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 -------------

题目描述：

就是求那个给出的公式，只考虑红色0-255像素值，给出每个颜色的像素点个数，要求把这些像素点变为最多k种像素值。求\(\sum _{i=1}^{n} \underset{1\leqslant i\leqslant k}{min}\left ( r_i-v_j\right )^2\)。每个像素原来的颜色与现在和它绝对值最小的元素的差值平方求和

解题思路：

dp的思想，0-255，时间复杂度：\(O(n^3)\)都可以，所以我们设 dp[i][j] :表示颜色分布0-i，变为最多j种颜色的答案。fx[i][j]:表示将颜色区间[i,j] 的颜色变为同样的某一种颜色的最小值。那么转移方程\(dp(i,j)=\underset{0\leq k\leq i}{min}(dp(k,j-1)+f(k+1,i))\)

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;

}

相关文章