八月洛谷训练记录

7.30 day 1

P2392 kkksc03考前临时抱佛脚

数组长度20，直接爆搜. 注意这里要从左往右搜，不能乱序搜，乱序的复杂度$O(n!)$，20也受不住啊

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
bool v[25];
int a[25];
int res;
int l, r;
void dfs(int tot, int now)
{
	if(now > tot){
		res = min(res, max(l, r));
		return;
	}
	l += a[now];
	dfs(tot, now + 1);
	l -= a[now];
	r += a[now];
	dfs(tot, now + 1);
	r -= a[now];
}
signed main()
{
	DDLC_ESCAPE_PLAN_FAILED;
	int s[5];
	fors(i, 1, 4) cin >> s[i];
	int ans = 0;
	fors(i, 1, 4){
		mem(v);
		res = inf;
		l = r = 0;
		fors(j, 1, s[i]) cin >> a[j];
		dfs(s[i], 1);
		ans += res;
	}
	cout << ans << endl;
	return 0;
}

P1441 砝码称重

依然是搜索，只不过搜索终点套了一个01背包。

依然提醒我，搜索一定要顺次，不要乱序，不然就T傻。

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
int n, m;
int a[25];
bool v[25] = {0};
bool f[2005];
int sum;
int ans = 0;
void dfs(int num, int last)
{
	if(num == m){
		mem(f);
		int cnt = 0;
		f[0] = 1;
		fors(i, 1, n){
			if(v[i]) continue;
			for(int j = sum; j - a[i] >= 0; --j){
				if(!f[j] && f[j - a[i]]) cnt++;
				f[j] |= f[j - a[i]];
			}
		}
		ans = max(ans, cnt);
		return;
	}
	fors(i, last + 1, n){
		if(!v[i]){
			v[i] = 1;
			dfs(num + 1, i);
			v[i] = 0;
		}
	}
}
signed main()
{
	DDLC_ESCAPE_PLAN_FAILED;
	cin >> n >> m;
	sum = 0;
	fors(i, 1, n) cin >> a[i], sum += a[i];
	dfs(0, 0);
	cout << ans << endl;
	return 0;
}

P3370 【模板】字符串哈希

1. 使用进制哈希法，让每个字母对应唯一一个数字，然后按进制运算，整个字符串对应一个唯一数字。为防止结果数字过大，对质数取模。不放心冲突的话可以再加上一个小质数。如果想省空间，那就得排序，用$log$时间复杂度换空间。

2. 使用trie树，平均复杂度$O(nlog|s|)$（代码是进制哈希）

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int mod = 1e9 + 7;
const int prime = 711451417;
int a[10005];
int hashe(string s)
{
	int ans = 0;
	for(auto x : s){
		ans = (ans * 117 + (int)x) % mod + prime;
	}
	return ans;
}
signed main()
{
	DDLC_ESCAPE_PLAN_FAILED;
	int t;
	cin >> t;
	int ans = 0;
	fors(i, 1, t){
		string s;
		cin >> s;
		a[i] = hashe(s);
	}
	sort(a + 1, a + 1 + t);
	fors(i, 1, t){
		if(a[i] != a[i - 1]) ans++;
	}
	cout << ans << endl;
	return 0;
}

P1621 集合

用线性筛预处理1e5内的素数，然后在区间内枚举每个质数的倍数，通过并查集合并。

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a, b, p;
int fa[maxn];
int prime[maxn];
const int N = 2e7 + 10;
bool is[N];
int cnt = 0;
void Prime(){
	mem(is);
	is[0] = is[1] = 1;
	for (int i = 2; i < N; ++i) {
		if(!is[i]) prime[cnt++] = i;
		for(int j = 0; j < cnt && prime[j] * i < N; ++j){
			is[prime[j] * i] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}
int find(int x)
{
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void join(int x, int y)
{
	int fx = find(x), fy = find(y);
	if(fx == fy) return;
	fa[fy] = fx;
}
signed main()
{
	DDLC_ESCAPE_PLAN_FAILED;
	Prime();
	cin >> a >> b >> p;
	fors(i, a, b) fa[i] = i;
	int x = 0;
	while(prime[x] < p) x++;
	for(int i = x; prime[i] <= b; ++i){
		int s = prime[i];
		while(s < a) s += prime[i];
		vector<int> v;
		while(s <= b){
			v.pb(s);
			s += prime[i];
		}
		for(int i = 1; i < v.size(); ++i){
			join(v[i], v[i - 1]);
		}
	}
	int ans = 0;
	fors(i, a, b) if(fa[i] == i) ans++;
	cout << ans << endl;
	return 0;
}

7.31 day 2

出去太久了加上在补cf的题以及写题解，没时间写洛谷的题orz

P1892 [BOI2003] 团伙

复习一下最基本的带权并查集。其实用反集概念即可。

顺便回归一下最朴素的码风

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
int fa[maxn];
int n, m;
int find(int x)
{
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void join(int x, int y){
	int fx = find(x), fy = find(y);
	if(fx == fy) return;
	fa[fy] = fx;
}
int main()
{
	// 敌人：合并n+x,y
	cin >> n >> m;
	for(int i = 1; i <= 2 * n; ++i) fa[i] = i;	
	for(int i = 0; i < m; ++i){
		char x;
		int l, r;
		cin >> x >> l >> r;
		if(x == 'F') join(l, r);
		else join(l, r + n), join(r, l + n);
	}
	int cnt = 0;
	for(int i = 1; i <= 2 * n; ++i){ if(fa[i] == i) cnt++;}
	cout << cnt << endl;
	return 0;
}

P4305 [JLOI2011]不重复数字

可以用拉链哈希做。懒得写了，但是哈希题写unordered_map太敷衍，于是写了个排序

#include <bits/stdc++.h>
// #define int long long
using namespace std;
const int maxn = 5e4 + 10;
struct node
{
	int x, id;
}a[maxn];
bool cmp(const node& x, const node& y){
	if(x.x != y.x) return x.x < y.x;
	return x.id < y.id;
}
bool re(const node& x, const node& y){
	return x.id < y.id;
}
signed main()
{
	int t;
	scanf("%d", &t);
	while(t--){
		int n, x;
		scanf("%d", &n);
		for(int i = 0; i < n; ++i){ scanf("%d", &a[i].x); a[i].id = i; }
		sort(a, a + n, cmp);
		vector<node> v;
		v.push_back(a[0]);
		for(int i = 1; i < n; ++i){
			if(a[i].x != a[i - 1].x){
				v.push_back(a[i]);
			}
		}
		sort(v.begin(), v.end(), re);
		for(auto x : v){
			printf("%d ", x.x);
		}
		printf("\n");
	}
	return 0;
}

8.1 day 3

P3405 [USACO16DEC]Cities and States S

如果组合是$a,b$，从$b,a$保存的容器中获得贡献，然后向$a,b$容器加1。

#include <bits/stdc++.h>
using namespace std;
int main()
{
	unordered_map<string, int> mp;
	int n;
	cin >> n;
	int ans = 0;
	for(int i = 0; i < n; ++i) {
		string a, b;
		cin >> a >> b;
		if(a.substr(0, 2) == b.substr(0, 2));
		else{
			mp[a.substr(0, 2) + b]++;
			ans += mp[b + a.substr(0, 2)];
		}
	}
	cout << ans << endl;
	return 0;
}

P3879 [TJOI2010]阅读理解

map裸题

#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, x;
	cin >> n;
	map<string, bool> mp[n + 1];
	for(int i = 0; i <= n; ++i){
		string s;
		getline(cin, s);
		stringstream ss;
		ss << s;
		ss >> x;
		while(ss >> s){
			mp[i][s] = 1;
		}
	}
	int m;
	cin >> m;
	for(int i = 0; i < m; ++i){
		string s;
		cin >> s;
		for(int j = 1; j <= n; ++j){
			if(mp[j].count(s)){
				cout << j << ' ';
			}
		}
		cout << endl;
	}
	return 0;
}

P3916 图的遍历

反向dfs，求较大的点能去哪些点，这样就能进行不回溯的dfs了。

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> v[100005];
int ans[100005] = {0};
void dfs(int i, int f)
{
	for (auto x : v[i]) {
		if (!ans[x]) {
			ans[x] = f;
			dfs(x, f);
		}
	}
}
int main()
{
	cin >> n >> m;
	// n次bfs，复杂度O(n(n+m)), 不可接受
	// n次dfs，不访问已经访问过的节点，复杂度O(n+m)，好！
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		v[y].push_back(x);
	}
	for (int i = n; i >= 1; --i) {
		if(!ans[i]) ans[i] = i;
		dfs(i, i);
	}
	for (int i = 1; i <= n; ++i ) {
		cout << ans[i] << ' ';
	}
	return 0;
}

8.2 day 4

学习网络流算法+摸鱼

8.3 day 5

多校自闭+摸鱼

8.4 day 6

今天摸摸Unity，诶嘿……

8.5 day 7

多校自闭，摸了会Unity，感觉最近状态很差……依然没有做洛谷。

8.6 day 8

伞兵才会一天玩五六个小时bf

8.7 day 9

P1918 保龄球

水题，找找状态（洛谷100AC纪念，2021-08-07 12:19:41）

/**
  * @file    :vsDebug.cpp
  * @brief   :
  * @date    :2021-08-05
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    unordered_map<int, int> mp;
    int n;
    cin >> n;
    fors(i, 1, n){
        int x;
        cin >> x;
        mp[x] = i;
    }
    int q;
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        cout << mp[x] << endl;
    }
    return 0;
}

P2814 家谱

评测机出锅了，下载下来和std输出一模一样判我wa了，不管了

字符串并查集

/**
  * @file    :vsDebug.cpp
  * @brief   :
  * @date    :2021-08-05
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
unordered_map<string, string> fa;
string find(string x){
    if(fa[x] == x){
        return x;
    }
    return fa[x] = find(fa[x]);
}
void join(string x, string y){
    string fx = find(x), fy = find(y);
    fa[fy] = fx;
}
signed main()
{
    // DDLC_ESCAPE_PLAN_FAILED;
    // freopen("out.txt", "w", stdout);
    string s;
    string f;
    while(getline(cin, s) && s != "$"){
        if(s[0] == '#'){
            f = s.substr(1, s.size() - 1);
            if(!fa.count(f)) fa[f] = f;
        }
        else if(s[0] == '+'){
            if(!fa.count(f)) fa[f] = f;
            if(!fa.count(s.substr(1, s.size() - 1))) fa[s.substr(1, s.size() - 1)] = s.substr(1, s.size() - 1);
            join(f, s.substr(1, s.size() - 1));
        }
        else{
            string u = s.substr(1, s.size() - 1);
            if(!fa.count(u)) fa[u] = u;
            cout << u << ' ' << find(u) << endl;
        }
    }
    return 0;
}

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

二叉堆基础题

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;

signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> q;
    int x;
    fors(i, 1, n){
        cin >> x;
        q.push(x);
    }
    int ans = 0;
    while(q.size() > 1){
        int x = q.top(); q.pop();
        int y = q.top(); q.pop();
        ans += x + y;
        q.push(x + y);
    }
    cout << ans << endl;
    return 0;
}

P1168 中位数

优先队列好例题，维护一个大顶堆和一个小顶堆即可

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;

signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    priority_queue<int> q;
    priority_queue<int, vector<int>, greater<int>> gq;
    int n;
    cin >> n;
    int x;
    int mid;
    cin >> x;
    cout << (mid = x) << endl;
    fors(i, 2, n){
        cin >> x;
        if(x > mid) gq.push(x);
        else q.push(x);
        while(gq.size() > q.size()){
            q.push(mid);
            mid = gq.top();
            gq.pop();
        }
        while(q.size() > gq.size()){
            gq.push(mid);
            mid = q.top();
            q.pop();
        }
        if(i & 1) cout << mid << endl;
    }
    return 0;
}

P2085 最小函数

维护一个容量为m的优先队列即可。

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;

signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int n, m;
    cin >> n >> m;
    priority_queue<int> q;
    while(n--){
        int a, b, c;
        cin >> a >> b >> c;
        int x = 1;
        while(1){
            int fx = a * x * x + b * x + c;
            if(q.size() < m || (q.size() >= m && q.top() > fx)){
                q.push(fx);
                if(q.size() > m) q.pop();
            }
            else break;
            x++;
        }
    }
    vector<int> ans;
    while(!q.empty()){
        ans.pb(q.top());
        q.pop();
    }
    for(int j = m - 1; j >= 0; --j){
        cout << ans[j] << ' ';
    }
    cout << endl;
    return 0;
}

P1631 序列合并

和上面P2085的思路很相近，都是找Top K. 这里不能算出所有答案，所以排序贪心一下。

/**
  * @file    :vsDebug.cpp
  * @brief   :
  * @date    :2021-08-07
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], b[maxn];
signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int n;
    cin >> n;
    fors(i, 1, n){
        cin >> a[i];
    }
    fors(i, 1, n){
        cin >> b[i];
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    priority_queue<int> q;
    fors(i, 1, n){
        fors(j, 1, n){
            if(q.size() >= n && a[i] + b[j] > q.top()) break;
            else q.push(a[i] + b[j]);
            if(q.size() > n) q.pop();
        }
    }
    vector<int> ans;
    fors(i, 1, n){
        ans.pb(q.top());
        q.pop();
    }
    for(int j = n - 1; j >= 0; --j){
        cout << ans[j] << ' ';
    }
    cout << endl;
    return 0;
}

8.8 day 10

P1801 黑匣子

和P1168一样，只不过这里不一定是中位数，而是位置随时可能改变

感觉还题目可以更进一步，位置左右任意移动

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = (int)(-2e9) - 1;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
queue<int> u;
signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int m, n;
    cin >> m >> n;
    priority_queue<int> q;
    priority_queue<int, vector<int>, greater<int>> gq;
    fors(i, 1, m) cin >> a[i];
    fors(i, 1, n){
        int x;
        cin >> x;
        u.push(x);
    }
    int mid = inf;
    int p = 0;
    fors(i, 1, m){
        if(mid == inf){
            gq.push(a[i]);
        }
        else if(a[i] > mid){
            gq.push(a[i]);
        }
        else{
            q.push(a[i]);
        }
        while(p && q.size() >= p){
            gq.push(mid);
            mid = q.top();
            q.pop();
        }
        while(u.front() == i){
            u.pop();
            if(mid != inf) q.push(mid);
            mid = gq.top();
            gq.pop();
            cout << mid << endl;
            p++;
        }
    }
    return 0;
}

P4053 [JSOI2007]建筑抢修

优先队列贪心

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
struct node
{
    int time;
    int limit;
}a[maxn];
bool cmp(const node& x, const node& y){
    return x.limit < y.limit;
}
signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int n;
    cin >> n;
    priority_queue<int> q;
    fors(i, 1, n) cin >> a[i].time >> a[i].limit;
    sort(a + 1, a + 1 + n, cmp);
    int time = 0;
    fors(i, 1, n){
        if(a[i].time + time > a[i].limit){
            if(a[i].time < q.top()){
                time -= q.top();
                q.pop();
                q.push(a[i].time);
                time += a[i].time;
            }
            continue;
        }
        q.push(a[i].time);
        time += a[i].time;
    }
    cout << (int)q.size() << endl;
    return 0;
}

8.9 day 11

没打

8.10 day 12

P2613 【模板】有理数取余

多校之后，再复习一下分数取模

以后分数取逆元再也不查资料惹

/**
  * @file    :vsDebug.cpp
  * @brief   :
  * @date    :2021-08-10
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int mod = 19260817;

int fpow(int x, int p, int m)
{
    int ans = 1;
    while(p){
        if(p & 1) ans = (ans * x) % m;
        x = (x * x) % m;
        p >>= 1;
    }
    return ans;
}
int divi(int x, int y)
{
    return (x % mod * fpow(y, mod - 2, mod)) % mod;
}
signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int t;
    t = 1;
    while(t--)
    {
        int a = 0, b = 0;
        string s1, s2;
        cin >> s1 >> s2;
        for(int i = 0; i < s1.size(); ++i){
            a = (a * 10 + s1[i] - '0') % mod;
        }
        for(int i = 0; i < s2.size(); ++i){
            b = (b * 10 + s2[i] - '0') % mod;
        }
        if(b % mod == 0) cout << "Angry!" << endl;
        else
            cout << divi(a, b) << endl;
    }
    return 0;
}

8.11 day 13

8.12 day 14

这两天具体去干了什么我就不说了

感觉自己这也想干，那也想干

最后什么也没干成

确实是有B students的好奇心和求知欲

但是没有B students的远见，也缺乏A students的定力

最后自己的技能就是

四不像

什么也不会

这样子真的不好，回想一下高中老师是怎么教我的 其实我是有把一件事做好做精的能力的吧。只是面对的选择太多的时候，我会什么都尝试一下，然后浅尝辄止。

是时候好好想一想，我要的到底是什么，我应该去做什么

然后就去做，不要再去看哪个可以搞哪个有意思了，我什么也不看，我只做好自己之前想做的

多学点知识吧。

8.13 day 15

P3865 【模板】ST 表

今天学ST表~

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
// #define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int f[maxn][30];
int n;
void process()
{
    for(int i = 1; i <= n; i ++) f[i][0] = a[i]; 
    int t = log(n) / log(2) + 1;
    for(int j = 1; j < 20; j ++)
    {
        for(int i = 1; i <= n - (1 << j) + 1; i ++)
        {
            f[i][j] = max(f[i][j-1],f[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int query(int x, int y){
    int t = log(abs(y-x + 1))/ log(2);
    int a = f[x][t];
    int b = f[y - (1 << t) + 1][t];
    return max(a,b);
}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
signed main()
{
    // DDLC_ESCAPE_PLAN_FAILED;
    int m;
    int l, r;
    n = read();
    m = read();
    fors(i, 1, n) a[i] = read();
    process();
    while(m--){
        l = read();
        r = read();
        printf("%d\n", query(l, r));
    }
    return 0;
}