Study notes of the first week of sophomore year

Wednesday

P3586 [POI2015]LOG（ Guess the conclusion + Dynamic open point line segment tree ）

First guess a conclusion

Greater than or equal to s You can definitely choose

Less than s As long as the sum of is greater than the remaining number to be selected multiplied by s That's it

Maintain with dynamic open point line segment tree

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
int ls[N << 6], rs[N << 6], a[N], cnt, n, m, root;           // Be careful root Must be set to... At first 0
ll t1[N << 6], t2[N << 6];

void up(int k) 
{ 
	t1[k] = t1[ls[k]] + t1[rs[k]];
	t2[k] = t2[ls[k]] + t2[rs[k]];
}

void modify(int& k, int l, int r, int x, int p)
{
	if(!k) k = ++cnt;                                // Dynamic opening point 
	if(l == r)
	{
		t2[k] += p;
		t1[k] = t2[k] * x;
		return;
	}
	int m = l + r >> 1;
	if(x <= m) modify(ls[k], l, m, x, p);
	else modify(rs[k], m + 1, r, x, p);
	up(k);
}

ll query1(int k, int l, int r, int L, int R)
{
	if(!k) return 0;                                 // When asking, the empty node returns 0
	if(L <= l && r <= R) return t1[k];
	int m = l + r >> 1; ll res = 0;
	if(L <= m) res += query1(ls[k], l, m, L, R);
	if(R > m) res += query1(rs[k], m + 1, r, L, R);
	return res;
}

int query2(int k, int l, int r, int L, int R)
{
	if(!k) return 0;
	if(L <= l && r <= R) return t2[k];
	int m = l + r >> 1, res = 0;
	if(L <= m) res += query2(ls[k], l, m, L, R);
	if(R > m) res += query2(rs[k], m + 1, r, L, R);
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	modify(root, 0, 1e9, 0, n);  
	while(m--)
	{
		char op[5]; int x, y;
		scanf("%s%d%d", op, &x, &y);
		if(op[0] == 'U')
		{
			modify(root, 0, 1e9, a[x], -1); 
			modify(root, 0, 1e9, a[x] = y, 1);
		}
		else
		{
			int t = query2(root, 0, 1e9, y, 1e9);
			ll sum = query1(root, 0, 1e9, 0, y - 1); 
			if(sum >= 1LL * (x - t) * y) puts("TAK");
			else puts("NIE");
		}
	}

	return 0;
}

P3809 【 Templates 】 Suffix sort

Suffix array template

/*
    sa[i]  Ranked as i The position of the suffix 
    height lcp(sa[i], sa[i - 1])  The ranking is i The suffix and rank of i−1 The longest common prefix of the suffix 
    H[i]：height[rak[i]], namely i The longest common prefix between the suffix number and the suffix before it 

     The longest public substring （ Can overlap ） height Array maximum   Because the ranking of the two substrings of the longest common prefix must be adjacent 
     Essentially different number of strings   Enumerate each suffix i  The contribution to the answer is  len − sa[i] + 1 − height[i]
     The largest common prefix of two suffixes   Make x=rank[i],y=rank[j],x < y, that lcp(i,j)=min(height[x+1],height[x+2]…height[y]).lcp(i,i)=n-sa[i].  use ST Table or segment tree 
*/

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e6 + 10;
int x[N], y[N], c[N], sa[N], rk[N], height[N], wt[30];
int n, m;
char s[N];

void get_SA()
{
    _for(i, 1, n) ++c[x[i] = s[i]];
    _for(i, 2, m) c[i] += c[i - 1];
    for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
    for(int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        _for(i, n - k + 1, n) y[++num] = i;
        _for(i, 1, n) if(sa[i] > k) y[++num] = sa[i] - k;
        _for(i, 1, m) c[i] = 0;
        _for(i, 1, n) ++c[x[i]];
        _for(i, 2, m) c[i] += c[i - 1];
        for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1; num = 1;
        _for(i, 2, n) 
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
        if(num == n) break;
        m = num;
    }
}

void get_height()
{
    int k = 0;
    _for(i, 1, n) rk[sa[i]] = i;
    _for(i, 1, n)
    {
        if(rk[i] == 1) continue;
        if(k) k--;
        int j = sa[rk[i] - 1];
        while(j + k <= n && i + k <= n && s[i + k] == s[j + k]) k++;
        height[rk[i]] = k;
    }
}

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    m = 122;                //m Represents the number of characters  ascll('z')=122 
                            // The range of the barrel is 1~m
    get_SA();
    _for(i, 1, n) printf("%d ", sa[i]);

    return 0;
}

Sunday

I have done some problems recently , I haven't sorted it out , Now tidy up

After the game mentality must be better , Calm and stressed

Don 't be nervous , Too much to compare

bzoj 1406（ Factor ）

Can be launched n | (x + 1)(x - 1)

Make n = a * b

a | (x + 1) And b | (x - 1)

or

b | (x + 1) And a | (x - 1)

So the root enumeration factor , Then enumerate the multiples of the factors

The multiple of the factors in the second half of the enumeration is obviously better

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

set<int> ans;

int main()
{
	int n; scanf("%d", &n);
	for(int a = 1; a * a <= n; a++)
		if(n % a == 0)
		{
			int b = n / a;
			for(int i = 0; i < n - 1; i += b) if((i + 2) % a == 0) ans.insert(i + 1);
			for(int i = b; i < n + 1; i += b) if((i - 2) % a == 0) ans.insert(i - 1);
		}
	
	if(ans.empty()) puts("None");
	else for(int x: ans) printf("%d\n", x);
	
	return 0;
}

CF877D Olya and Energy Drinks（bfs + prune ）

The key to this problem is pruning

When I write , Cut less T, Cut too much WA

The key is to expand

If f[x][y] + 1> f[xx][yy]

At this time, it's direct break Because later points can pass f[xx][yy] To expand , Time is the same

If f[x][y] + 1 == f[xx][yy] Don't join the queue at this time , But we should continue to expand

Next, it may be expanded to more excellent points

It's not hard , Just too nervous to expect

Tonight's game must be sinking , calm , Treat with an ordinary mind

My opponent tonight is myself , No one else . It's about your mentality

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)  
using namespace std;

const int N = 1e3 + 10;
int f[N][N], n, m, k;
char s[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
struct node
{
	int x, y, step;
};
 
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	_for(i, 1, n) scanf("%s", s[i] + 1);

	int x1, y1, x2, y2;
	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

	queue<node> q;
	q.push(node{x1, y1, 0});
	memset(f, 0x3f, sizeof f);
	f[x1][y1] = 0;

	while(!q.empty())
	{
		node u = q.front(); q.pop();
		int x = u.x, y = u.y;
		if(u.step != f[x][y]) continue;

		rep(j, 0, 4)
			_for(i, 1, k)
			{
				int xx = x + dir[j][0] * i, yy = y + dir[j][1] * i;
				if(xx < 1 || xx > n || yy < 1 || yy > m || s[xx][yy] == '#' || f[xx][yy] <= f[x][y]) break;
				if(f[x][y] + 1 < f[xx][yy])
				{
					f[xx][yy] = f[x][y] + 1;
					q.push(node{xx, yy, f[xx][yy]});
				}
			}
	}

	if(f[x2][y2] > 1e9) puts("-1");
	else printf("%d\n", f[x2][y2]);
	
	return 0;
}

T199660 tree（ Recurrence ）

Two recursions are examined

First of all, we can find , about n, It can be divided into several same trees

So we can first find out how many construction methods there are for a tree

And then ask n How many construction methods are there for each node

For a tree , It's understandable

Remove the root node , That's all n-1 Nodes , this n-1 Nodes can be 1 A daughter tree , That is to say dp[n - 1]

Can be 2 Divide by two subtrees , Just dp[(n - 1) / 2]

So just enumerate the factors

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)  
using namespace std;

const int mod = 998244353;
const int N = 1e5 + 10;
int dp[N], ans[N], n;
 
int main()
{
	scanf("%d", &n);
	dp[1] = dp[2] = 1;
	_for(i, 3, n)
		for(int j = 1; j * j <= i - 1; j++)
			if((i - 1) % j == 0)
			{
				dp[i] = (dp[i] + dp[j]) % mod;
				if(j * j != i - 1) dp[i] = (dp[i] + dp[(i - 1) / j]) % mod;
			}
				
	int ans = 0;
	for(int i = 1; i * i <= n; i++)
		if(n % i == 0)
		{
			ans = (ans + dp[i]) % mod;
			if(i * i != n) ans = (ans + dp[n / i]) % mod;
		}
	printf("%d\n", ans);
	
	return 0;
}