当前位置：网站首页>Codeforces Round ＃803 (Div. 2)

Codeforces Round ＃803 (Div. 2)

2022-06-29 11:02:00 【Zqchang】

目录


时隔半年，重返cf，第一场就打的稀碎

A

A. XOR Mixup
只能说很亲切，水题
就是自己dev又卡bug了，tnnd

#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 = 110;
int a[N];
int t, n;
signed main()
{
    
	fast;
	cin >> t;
	while(t--)
	{
    
		cin >> n;
		for(int i=1; i<=n; i++) cin >> a[i];
		int res;
		for(int i=1; i<=n; i++)
		{
    
			res = 0;
			for(int j=1; j<=n; j++)
			{
    
				if(i == j) continue;
				res ^= a[j];	
			}
// puts("111");
			if(res == a[i]) 
			{
    
				cout << res << endl;
				break;
			}
// else puts("!!");
		}
	}
	return 0;
}

B. Rising Sand

B. Rising Sand

读完之后，感觉非常nt，然后写完交了一次，wa，然后发现忘了特判k=1

#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 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 = 2e5 + 10;

int t, n, m;
int a[N];
signed main()
{
    
	fast;
	cin >> t;
	while(t--)
	{
    
		cin >> n >> m;
		for(int i=1; i<=n; i++) cin >> a[i];
		
		if(m == 1)
		{
    
			cout << (n - 1) / 2 << endl;
			continue;
		}
		
		int res = 0;
		for(int i=2; i<n; i++)
		{
    
			if(a[i] > a[i-1] + a[i+1]) res ++;
		}
		cout << res << endl;
	}
	return 0;
}

C. 3SUM Closure

C. 3SUM Closure

比较有意思，就是说，有一个数组，里面任选ijk三个下标，他们的数组对用数的和，要还在数组内，就是一个好数组，然后问你数组是不是，一开始想的是，排个序，看看前三个数的和 和后三个数的和是不是都在数组里面就可以，然后发现不对劲，因为开头和结尾可能不相等，还有一种类似-2, -1, 1, 1这种情况其实是NO，也会输出YES，出去这两种就对了
也就是

#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 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 = 2e5 + 10;

int t, n, m;
int a[N];
set<int> s;
signed main()
{
    
	fast;
	cin >> t;
	while(t--)
	{
    
		s.clear();
		cin >> n;
		int num = 0;
// bool flag = 
		for(int i=1; i<=n; i++) 
		{
    
			cin >> a[i];
			s.insert(a[i]);
			if(a[i] != 0) num ++;
		}
		
		if(n == 4)
		{
    
			bool flag = 0;
			for(int i=1; i<=4; i++)
			{
    
				for(int j=i+1; j<=4; j++)
				{
    
					for(int k=j+1;k<=4; k++)
					{
    
						int a1 = a[i] + a[j] + a[k];
						if(!s.count(a1)) 
						{
    
							cout << "NO" << endl;
							flag = 1;
							break;
						}
					}
					if(flag) break;
				}
				if(flag) break;
			}				
			if(!flag) cout << "YES" << endl;
			continue;
		}
		
		sort(a + 1, a + 1 + n);
		int a1 = a[1] + a[2] + a[3];
		int a2 = a[n] + a[n - 1] + a[n - 2];
		if(s.count(a1) && s.count(a2)) 
		{
    
			if(num == 2)
			{
    
				if(a1 == -a2)
				{
    
					cout << "YES" << endl;
					continue;
				}
				else
				{
    
					cout << "NO" << endl;
					continue;
				}
			}
			cout << "YES" << endl;//就是开头和结尾可能不相等,还有一种类似-2, -1, 1, 1这种情况其实是NO 
		}
		else cout << "NO" << endl;
		
	}
	return 0;
}

还有另一种最开始A掉的，其实就是找个规律吧
根据n为3和4的时候暴力判断
之后中间铁定是0，就找不等于0的个数num，全是0和num小于1可以，num>2不行，num=2的时候互为相反数可以

#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 = 2e5 + 10;
int t, n, a[N];
set<int> s;
signed main()
{
    
	cin >> t;
	while(t--)
	{
    
		s.clear();
		cin >> n;
		int num = 0;
		for(int i=1;i<=n; i++) 
		{
    
			cin >> a[i];
			if(a[i] != 0) num ++;
			s.insert(a[i]);
		}
		
		
		if(n == 3) 
		{
    
			int aa = a[1] + a[2] + a[3];
			if(s.count(aa))
			{
    
				cout << "YES" << endl;
				continue;
			}
			else
			{
    
				cout << "NO" << endl;
				continue;
			}
				
		}
		
		
		if(n == 4)
		{
    
			bool flag = 0;
			for(int i=1; i<=4; i++)
			{
    
				for(int j=i+1; j<=4; j++)
				{
    
					for(int k=j+1;k<=4; k++)
					{
    
						int a1 = a[i] + a[j] + a[k];
						if(!s.count(a1)) 
						{
    
							cout << "NO" << endl;
							flag = 1;
							break;
						}
					}
					if(flag) break;
				}
				if(flag) break;
			}
				
					
			if(!flag) cout << "YES" << endl;
			continue;
		}
		
		if(num > 2) 
		{
    
			cout << "NO" << endl;
			continue;
		}
		else if(num <= 1) 
		{
    
			cout << "YES" << endl;
			continue;
		}
		else
		{
    
			sort(a + 1, a + 1 + n);
			if(a[1] == -a[n])
			{
    
				cout << "YES" << endl;
				continue;
			}
			else
			{
    
				cout << "NO" << endl;
				continue;
			}
		}
	}
	return 0;
}

D. Fixed Point Guessing

D. Fixed Point Guessing
一个交互题，第一次做，有点新颖
不难理解，给你奇数个数，然后从里面给数配对，有一个单独的不动，其他的交换位置，然后你可以每次给个区间，他给你原数组排序后的结果，询问不能超过十五次，问你单独的数是什么，二分加讨论

就是每次找不在这区间的数的个数，然后看看在这个区间的数有几个，奇数个里面有答案，一直二分就可以

#include<map>
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#define up(i, x, y) for(int i = x; i <= y; i++)
#define down(i, x, y) for(int i = x; i >= y; i--)
#define maxn ((int)5e5 + 10)
#define INF 0x3f3f3f3f

typedef long long ll;

using namespace std;

vector<int> vec;

int main()
{
    
    int T; cin >> T; while(T--)
    {
    
        int n; cin >> n;
        int ans = -1;
        int tim = 15;
        int l = 1, r = n;
        while(l < r)
        {
    
            int mid = (l + r) >> 1;
            cout << "? " << l << " " << mid << endl;
            cout.flush();
            int num = 0;
            for(int i = 0; i < mid - l + 1; ++i)
            {
    
                int x; cin >> x;
                if(x < l || x > mid) num++;
            }
            if( (mid - l + 1 - num) & 1 ) r = mid;
            else l = mid + 1;
        }

        std::cout << "? " << l << " " << l << std::endl;
        int x; cin >> x;
      	cout << "! " << l << endl;
        cout.flush();
    }
}
原网站

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

边栏推荐

猜你喜欢

随机推荐