LA 4255 Guess

痛定思痛。 2021-12-13 23:21 118阅读 0赞

题目链接：[https://icpcarchive.ecs.baylor.edu/index.php?option=com\_onlinejudge&Itemid=8&page=show\_problem&problem=2256][https_icpcarchive.ecs.baylor.edu_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_2256]

题意：给定一串数字a1,a2....an，给出sij的正负数值。sij代表ai+...aj的大小。求一组结果满足此条件。-10<=ai<=10.

思路：

设：Bi = a1+ a2 + ... ai，则，我们可以求出Bj和Bi-1的大小关系。可以由大到小连一条有向边，对此有向图做拓扑排序。

拓扑排序的做法如下：我们规定节点初始值：Bk =0（这只是一个相对值，事实上我们求的ai是Bi与Bi-1的差值，所以Bi初始是什么都没有关系，我们求得是相对差）.

如果Bi 向Bj有一条有向边，那么Bi>Bj,说明Bi至少比Bj大1，我们用v\[k\]记录Bk的值，不断调整此数值。最终就能求得一组解。

#include <stdio.h>
    #include <stdlib.h>
    #include <vector>
    #include <queue>
    #include <iostream>
    
    using namespace std;
    
    #define Maxn 20
    vector<int> g[Maxn];
    int indeg[Maxn],v[Maxn];
    int n;
    
    void init()
    {
    	for(int i=0;i<Maxn;i++) 
    	{
    		g[i].clear();
    		indeg[i] = 0;
    		v[i] = 0;
    	}
    }
    
    void toposort()
    {
    	queue<int> q;
    	for(int i=0;i<=n;i++)
    	{
    		if(indeg[i] == 0) q.push(i);
    	}
    	while(!q.empty())
    	{
    		int s = q.front();
    		q.pop();
    		for(int i=0;i<g[s].size();i++)
    		{
    			int t = g[s][i];
    			v[t] = min(v[t],v[s]-1);
    			if(--indeg[t] == 0)
    			{
    				q.push(t);
    			}
    		}
    	}
    }
    void output()
    {
    	for(int i=1;i<=n;i++)
    	{
    		if(i!=n) printf("%d ",v[i]-v[i-1]);
    		else printf("%d\n",v[i]-v[i-1]);
    	}
    }
    int main()
    {
    	#ifndef ONLINE_JUDGE
    		freopen("in.txt","r",stdin);
    	#endif
    	int t;
    	char str[20];
    	scanf(" %d",&t);
    	while(t--)
    	{
    		init();
    		scanf(" %d",&n);
    		scanf("%s",str);
    		for(int i=1,p=0;i<=n;i++)
    		{
    			for(int j=i;j<=n;j++,p++)
    			{
    				if(str[p] == '-')
    				{
    					g[i-1].push_back(j);
    					indeg[j]++; 
    				}
    				else if(str[p] == '+')
    				{
    					g[j].push_back(i-1);
    					indeg[i-1]++;
    				}
    			}
    		}
    		toposort();
    		output();
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/james1207/p/3366084.html

[https_icpcarchive.ecs.baylor.edu_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_2256]: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2256