2024.2.15 寒假训练记录（24）

水题就不写了

多思考

CF 1931F Chat Screenshots

题目链接

抑郁了这场的F不难但还是没做出来

我的思路是利用前两个判断出正确的顺序，然后依次验证是否合法，但是会有特殊情况让两个判断不出唯一的正确顺序

实际上可以用拓扑排序解决这个问题，也就是记住每两人的相对顺序，每次加边，最后只要图上有环就说明有矛盾，于是转化成有向图判环问题

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
   
	int n, k;
	cin >> n >> k;
	vector<vector<int>> g(n + 1);
	vector<int> ind(n + 1);
	for (int i = 0; i < k; i ++ )
	{
   
		vector<int> a(n);
		for (int i = 0; i < n; i ++ )
		{
   
			cin >> a[i];
			if (i > 1)
			{
   
				g[a[i - 1]].push_back(a[i]);
				ind[a[i]] ++ ;
			}
		}
	}
	queue<int> q;
	vector<bool> st(n + 1);
	for (int i = 1; i <= n; i ++ )
	{
   
		if (ind[i] == 0)
		{
   
			q.push(i);
			st[i] = true;
		}
	}
	while (!q.empty())
	{
   
		auto t = q.front();
		q.pop();
		for (int i = 0; i < g[t].size(); i ++ )
		{
   
			int j = g[t][i];
			if (st[j]) continue;
			ind[j] -- ;
			if (ind[j] == 0)
			{
   
				q.push(j);
				st[j] = true;
			}
		}
	}
	for (int i = 1; i <= n; i ++ )
	{
   
		if (ind[i] != 0) 
		{
   
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
}

signed main()
{
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t -- )
	{
   
		solve();
	}
}

CF 1931G One-Dimensional Puzzle

题目链接

不算太难的组合数学问题，发现34号不会改变右侧的状态，所以排列数主要是看12号，又发现12号必须要交替出现，两者数量相差大于1肯定不行，其他情况都能组成链。

12的排列是固定的，剩下的就是往里面填34，套个组合数取模的模板

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 2e5 + 10;
const int maxn = 1e7 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int Jc[maxn];

void calJc() // 求 maxn 以内的数的阶乘 不知道开多少就1e6吧爆不了
{
   
    Jc[0] = Jc[1] = 1;
    for (int i = 2; i < maxn; i++)
        Jc[i] = Jc[i - 1] * i % mod;
}

int pow(int a, int n, int p) // 快速幂取模
{
   
    int ans = 1;
    while (n)
    {
   
        if (n & 1)
            ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

int niYuan(int a, int b) // 费马小定理求逆元
{
   
    return pow(a, b - 2, b);
}

int C(int a, int b) // 组合数
{
   
    if (a < b)
        return 0;
    return Jc[a] * niYuan(Jc[b], mod) % mod * niYuan(Jc[a - b], mod) % mod;
}

void solve()
{
   
    int c1, c2, c3, c4, c;
    cin >> c1 >> c2 >> c3 >> c4;
    int ans = 0;
    if (abs(c1 - c2) > 1)
    {
   
        cout << 0 << '\n';
        return;
    }
    if (c1 == c2)
    {
   
        if (c1 == 0 && c2 == 0)
        {
   
            if (c3 && c4) ans = 0;
            else ans = 1;
        }
        else
        {
   
            ans = (C(c1 + c3 - 1, c1 - 1) * C(c2 + c4, c2)) % mod;
            ans = (ans + (C(c1 + c3, c1) * C(c2 + c4 - 1, c2 - 1)) % mod) % mod;
        }
    } 
    else if (c1 > c2) ans = (C(c2 + c3, c2) * C(c2 + c4, c2)) % mod;
    else ans = (C(c1 + c3, c1) * C(c1 + c4, c1)) % mod;
    cout << ans << '\n';
}

signed main()
{
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    calJc();

    int t = 1;
    cin >> t;
    while (t--)
    {
   
        solve();
    }
}