牛客周赛 Round 49 (D~F)

嘤嘤不想求异或喵

think:首先l和r的范围有1e18,我们能要到要么是二分(但这题显然和二分无关),所以我们尝试打表找规律.打表发现x是4的倍数,1~x的异或和应该是x,同理其他也是有规律的.

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> pii;
const int N = 1e6 + 10;

int work(int x) {
    if (x % 4 == 0) return x;
    else if (x % 4 == 1) {
        return 1;
    } else if (x % 4 == 2) {
        int t = x / 4;
        return t * 4 + 3;
    } else return 0;
}
void solve() 
{
    /*这是打表的代码*/
    // int x = 0;
    // for (int i = 1; i <= 1e5; i ++ ) {
    //     x ^= i;
    //     cout << i << ' ' << x << '\n';
    // }
    int l, r;
    cin >> l >> r;
    cout << (work(l - 1) ^ work(r)) << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_ -- ){
        solve();
    }
    return 0;
}

嘤嘤不想解方程喵 

think:把第一个方程代入第二个后,我们会得到一个二元一次方程.接下来就是分类讨论,如果二次项系数不为零,根据b*b-4*a*c是否大于等于0来判断有几个解.如果二次项系数为0,若一次项系数不为0,有inf个解.一次项系数为0且常数为0则有0个解.

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
const int N = 1e6 + 10;
typedef pair<int, int> pii;
typedef long long ll;

void solve(){
        int res;
		ll a1,b1,c1,a2,b2,c2;
		cin>>a1>>b1>>c1>>a2>>b2>>c2;
		__int128 i,j,k,d;
		i=a1*b2;
		j=b1*b2+a2;
		k=c1*b2+c2;
		d=j*j-4*i*k;
		if(i==0){
			if(j==0){
				cout<<(k?"0\n":"INF\n");
			}
			else{
				cout<<"1\n";
			}
		}
		else{
			if(d<0)res=0;
			else if(d==0)res=1;
			else res=2;
			cout<<res<<'\n';
		}
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_ -- )
    {
        solve();
    }
    return 0;
}

嘤嘤不想找最小喵

think:这个公式告诉我们,a[i],a[i + k],a[i + 2k]应该是等差数列.然后它要求当前k长度下,所有的i都满足,等价于[1, n - 2 * i], [1 + i, n - i], [1 + 2 * i, n]这的和满足等差数列.所以我们可以用字符串哈希的方法来判断,字符串哈希的技巧是P取131, mod = 2^64(这里可以把数据类型定义成usigned long long刚好满足溢出就取模).

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define ull unsigned long long
const int N = 1e6 + 10;
const int P = 131;
typedef pair<int, int> pii;

int n, a[N];
ull h[N], p[N];

ull get_h(int l, int r) {
	return h[r] - h[l - 1] * p[r - l + 1];
}

void solve()
{
	cin >> n;
	p[0] = 1;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];	
	for (int i = 1 ;i <= n; i ++ ) {
		h[i] = h[i - 1] * P + a[i];
		p[i] = p[i - 1] * P;
	}

	for (int i = 1; i <= n; i ++ ) {
		ull a = get_h(1, n - 2 * i), b = get_h(1 + i, n - i), c = get_h(1 + 2 * i, n);
		if ((a + c) == 2 * b) {
			cout << i << '\n';
			return ;
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while (_ -- )
	{
		solve();
	}
	return 0;
}