1 条题解

  • 0
    @ 2023-11-25 18:43:21
    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 100000;
    int c, t;
    int n, m;
    //最后会变成谁或非谁(用对应负数表示非),0 表示和所有人初始值没关系 
    int x[MAXN + 5];
    //如果 x[i] 为 0,val[i] 表示会变成多少 
    char val[MAXN + 5]; 
    char myNot(char x)
    {
    	if (x == 'T')
    		return 'F';
    	if (x == 'F')
    		return 'T';
    	return 'U';	
    } 
    //n,m <= 10 
    namespace subtask1{
    	char ini[MAXN + 5]; //初始值设置的值
    	char temp[MAXN + 5]; //最终推理的值 
    	int ans;
    	void dfs(int now,int cnt)
    	{
    		if (now == n + 1)
    		{
    			//验证 
    			for(int i = 1; i <= n; i++)
    			{
    				if(x[i] == 0)
    					temp[i] = val[i];
    				else if(x[i] > 0)
    					temp[i] = ini[x[i]];
    				else if(x[i] < 0)
    					temp[i] = myNot(ini[-x[i]]);
    			} 
    			bool flag = true;
    			for(int i = 1; i <= n; i++)
    				if (ini[i] != temp[i])
    				{
    					flag=false;
    					break;
    				}
    			if (flag)
    				ans = min(ans, cnt);
    			return ;
    		}
    		ini[now] = 'T';
    		dfs(now+1, cnt);
    		ini[now] = 'F';
    		dfs(now+1, cnt);
    		ini[now] = 'U';
    		dfs(now+1, cnt+1);
    	}
    	void main()
    	{
    		ans = n;
    		dfs(1, 0);
    		cout << ans << "\n"; 
    	} 
    }
    //没有依赖 
    namespace subtask2{
    	void main()
    	{
    		int ans = 0;
    		for(int i = 1; i <= n; i++) 
    			if (x[i] == 0 && val[i] == 'U') 
    				ans++;
    		cout << ans << "\n";
    	}
    }
    //没有 - 
    namespace subtask3{
    	bool vis[MAXN + 5];
    	char f(int pos)
    	{
    		vis[pos] = true;
    		//如果当前为定值,返回对应值 
    		if (x[pos] == 0)
    			return val[pos];
    		//如果出现了环,这条路上都设置为真 
    		if (vis[x[pos]] == true && 
    			x[x[pos]] != 0){
    				
    			x[pos] = 0;
    			val[pos] = 'T';
    			return 'T';
    		}
    		val[pos] = f(x[pos]);
    		x[pos] = 0;	
    		return val[pos];
    	}
    	void main()
    	{
    		//推理最终值 
    		int ans = 0;
    		for(int i = 1; i <= n; i++)
    			vis[i] = false;
    		for(int i = 1; i <= n; i++) 
    		{ 
    			if (f(i) == 'U')
    				ans++;
    		} 
    		cout << ans << "\n";
    	}
    }
    //并查集,合并与某个数初值相等及不等的位置 
    namespace subtask4{
    	int tot, p[MAXN+5][2];//p[i][0] 和 i 相等的点、p[i][1] 和 i 不等的点 
    	int fa[MAXN * 2 + 10];
    	int findFa(int x)
    	{
    		if(x == fa[x])
    			return x;
    		return fa[x] = findFa(fa[x]);	
    	}
    	void mer(int x,int y)
    	{
    		int faX = findFa(x);
    		int faY = findFa(y);
    		fa[faX] = faY;
    	}
    	void main()
    	{
    		//给点编好号 
    		tot = 0;
    		for(int i = 1; i <= n; i++) 
    		{
    			p[i][0] = ++tot;
    			p[i][1] = ++tot;
    		}
    		//把相等关系与不等关系通过并查集加上去
    		for(int i = 1; i <= tot; i++)
    			fa[i] = i;
    		for(int i = 1; i <= n; i++)
    		{
    			if(x[i] == 0)
    			{
    				if(val[i] == 'U')
    					mer(p[i][0], p[i][1]);
    			}
    			else if(x[i] > 0)
    			{
    				mer(p[i][0], p[x[i]][0]);
    				mer(p[i][1], p[x[i]][1]);
    			}			
    			else if(x[i] < 0)
    			{
    				mer(p[i][0], p[-x[i]][1]);
    				mer(p[i][1], p[-x[i]][0]);
    			}
    		}
    		//输出要有几个 U 
    		int ans = 0;
    		for(int i = 1; i <= n; i++)
    			if(findFa(p[i][0]) == findFa(p[i][1]))
    				ans++;
    		cout << ans << "\n";
    	}
    }
    int main()
    {
    	freopen("tribool.in", "r", stdin);
    	freopen("tribool.out", "w", stdout);
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cin >> c >> t;
    	while (t--)
    	{
    		cin >> n >> m;
    		for (int i = 1; i <= n; i++)
    			x[i] = i;
    		while (m--)
    		{
    			char v;
    			int posI, posJ;
    			cin >> v;
    			if (v == 'T' || v == 'F' || v == 'U')
    			{
    				cin >> posI;
    				x[posI] = 0;
    				val[posI] = v;				
    			}
    			else if (v == '+')
    			{
    				cin >> posI >> posJ;
    				if (x[posJ] != 0)
    					x[posI] = x[posJ];				
    				else
    				{
    					x[posI] = 0;
    					val[posI] = val[posJ];	
    				}
    			}
    			else if (v == '-')
    			{
    				cin >> posI >> posJ;
    				if (x[posJ] != 0)
    					x[posI] = -x[posJ];				
    				else
    				{
    					x[posI] = 0;
    					val[posI] = myNot(val[posJ]);	
    				}	
    			}
    		}	
    		if(c <= 2)
    			subtask1::main();
    		else if(c <= 4)
    			subtask2::main();
    		else if(c <= 6)
    			subtask3::main();
    		else
    			subtask4::main();
    	}	
    	return 0;
    }
    
    • 1

    信息

    ID
    1364
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    8
    已通过
    1
    上传者