当前位置：网站首页>【LGR-109】洛谷 5 月月赛 II ＆ Windy Round 6

【LGR-109】洛谷 5 月月赛 II ＆ Windy Round 6

2022-07-06 04:43:00 【Zqchang】

P8344 「Wdoi-6」走在夜晚的莲台野

P8344 「Wdoi-6」走在夜晚的莲台野
这个就是推一个公式，比较简单，但是当时减号写成加号没看出来，无语，画了十多分钟

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
int x, y, z;
signed main()
{
    
	int t;
    cin >> t;
    while (t--)
    {
    
        cin >> x >> y >> z;
        int p = x * z - (x + 1) * x / 2 + z - x;

        if(x > z || p < y ) cout << "Merry" << endl;
        else cout << "Renko" << endl;
    }
    
	return 0;
}

P8345 「Wdoi-6」华胥之梦

P8345 「Wdoi-6」华胥之梦
有人瞎说图论，差点信了
也是个推式子的题，就直接写
在这里插入图片描述
赛时推的

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 1e6 + 10;
int a[N];
int n, c, q;

signed main()
{
    
	fast;
    cin >> n >> c >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> v;
    while(q --)
    {
    
        v.clear();
        int x, y; cin >> x;
        int sum = 0;
        for(int i=1; i<=x; i++) 
        {
    
            cin >> y;
            v.push_back(a[y]);
            sum += a[y];
        }
        sort(v.begin(), v.end());

        cout << (x - 1) * c - sum - v[x - 1] + 2 * v[0] << endl;
    }
	return 0;
}

P8346 「Wdoi-6」最澄澈的空与海

P8346 「Wdoi-6」最澄澈的空与海

这个题大意就是
在这里插入图片描述
在这里插入图片描述
这个题目找出来我代码的一些隐患吧
在这里插入图片描述
在这里插入图片描述
在洛谷，vector不能这么清空
1e6的读入差不多就要用快读了，注意STL，这里用set想去掉重边，给T了，裂开

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bitsdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e6 + 10;
int n, m, t;
vector<int> mp[N];
int in[N];
int u, v;
set<PII> s;
bool vis[N];
signed main()
{
    
	fast;
    cin >> t;
    while(t --)
    {
    
        cin >> n >> m;
        
        for(int i=1; i<=m; i++)
        {
    
            cin >> u >> v;
            v += n;
// if(s.count({u, v}) || s.count({v, u})) continue;
            mp[u].push_back(v);
            mp[v].push_back(u);
            in[u] ++ ;
            in[v] ++;
// s.insert({u, v});
        }
        
        n *= 2;
        int res = 0;
        queue<int> q;
        for(int i=1; i<=n; i++) if(in[i] == 1) q.push(i);
        while(q.size())
        {
    
            u = q.front();
            q.pop();
            if(vis[u] || in[u] != 1) continue;

            vis[u] = 1;
            in[u] --;
            for(auto i: mp[u])
            {
    
            	if(in[i] == 1 && !vis[i])
            	{
    
            		res ++;
            		in[i] --;
            		vis[i] = 1;
            	}
                else if(!vis[i]) 
                {
    
                	res ++;
                	vis[i] = 1;
                    for(auto j : mp[i])
                    {
    
						-- in[i];
						-- in[j];
                    	if(in[j] == 1 && !vis[j]) q.push(j);
					}
                    	
                }
            }
        }
        if(res == n / 2) cout << "Renko" << endl;
        else cout << "Merry" << endl;
    
// s.clear();
        for(int i=1; i<=n; i++) 
        {
    
            in[i] = 0;
            vis[i] = 0;
            mp[i].clear();
        }
    }
	return 0;
}

P8347 「Wdoi-6」另一侧的月

P8347 「Wdoi-6」另一侧的月

疑问和注意点在代码里面

大致方法就是，如果能找到
在这里插入图片描述
圈起来的这种结构，就一定是先手必胜，此外还有别的情况，不一一列举了，想看的自己看吧

参考1
参考2

!((n + 1) & n)讲一下这个判断，这是判断n+1是不是2的幂次方的，也就是能判断满二叉树，感觉参考1不应该过，有bug，我再想想

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
int in[N];
vector<int> v[N];
bool dfs(int u, int fa)
{
    
    for(auto i : v[u])
    {
    
        if(i == fa) continue;
        if(!(in[u] & 1) && in[i] == 1) return true;
        if(dfs(i, u)) return true;
    }
    return false;
}

signed main()
{
    
    int t;
    cin >> t;
    while (t--)
    {
    
        int n; cin >> n;
        
        
        int a, b;
        for(int i=1; i<n; i++)
        {
    
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
            in[a] ++;
            in[b] ++;
        }
        bool flag = 0;
		for(int i=1; i<=n; i++)
			if(in[i] != 2) flag = 0;
			
        if(dfs(1, -1) || !((n + 1) & n)) cout << "Hifuu" << endl;
		//!((n + 1) & n)这个判断的是是否为满二叉树，但是这个判断方法感觉不严谨，不知道为什么要特判 
		//同学有种写法，思路一样，但是他直接判断有没有度是2的点，也能过，就不用特判了 
        else cout << "Luna" << endl;
        
        for(int i=1; i<=n; i++)
		{
    
		 	in[i] = 0;
		 	v[i].clear();
		} 
    }
    
    return 0;
}
原网站

版权声明
本文为[Zqchang]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_51176105/article/details/125611681

边栏推荐

猜你喜欢

随机推荐