text-2020

http://acm.hdu.edu.cn/diy/contest_show.php?cid=36899

1010-我！是！签！到！题！：BFS

http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1010&cid=36899

思路：bfs，普通的用bfs求最短路是先到终点的路径最短，而这里又是最短里面的字典序最小，那么就不能上下左右的顺序任意选择了，而是优先选择小的字母去走，因为D<L<R<U,那么就按照下左右上的顺序去走。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

struct node{
	int x,y,num;
	string str;
	node(int a,int b,string s,int n){
		x = a;
		y = b;
		str = s;
		num = n;
	}
};

char s[105][105];
char dir[4] = {'D','L','R','U'};
int vis[105][105];
int d[4][2] = {{1,0},{0,-1},{0,1},{-1,0}};
int t,n,m,k,x,y;

bool check(int dx,int dy)
{
	if(dx >= 1 && dx <= n && dy >= 1 && dy <= m && !vis[dx][dy] && s[dx][dy] != '#')
	    return true;
	return false;
}

void bfs()
{
	queue<node>q;
	q.push(node(x,y,"",0));
	vis[x][y] = 1;
	while(!q.empty()){
		node st = q.front();
		q.pop();
		int dx,dy;
		if(s[st.x][st.y] == 'S') {
			cout << st.num << endl;
			cout << st.str << endl;
			break;
		}
		for(int i = 0; i < 4; i++){
			dx = st.x + d[i][0];
			dy = st.y + d[i][1];
			if(check(dx,dy)){
				vis[dx][dy] = 1;
				q.push(node(dx,dy,st.str+dir[i],st.num+1));
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
    cin >> t;
    while(t--){
    	cin >> x >> y;
    	cin >> n >> m;
    	memset(vis,0,sizeof(vis));
    	for(int i = 1; i <= n; i++){
    		cin >> s[i] + 1;
		}
		bfs();
	}
	return 0;
}

1001：欧拉函数

http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1001&cid=36899

1001的原题：https://vjudge.net/problem/LightOJ-1370

思路：根据题意可看出，我们要找出某个最小的数去满足获取全部香蕉，又因为gcd(x,y) != 1的话则咒语失效，所有我们先处理1-1e6中所有数在1-他自己与它互质的数有多少个。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

//牛牛的算术
int prime[1000005],phi[1000005];
void init()
{
    int cnt = 0;
    for(int i = 2; i <= 1000000; i++){
        if(!phi[i]){
            phi[i] = i - 1;
            prime[cnt++] = i;
        }
        for(int j = 0; j < cnt; j++){
            if(i * prime[j] > 1000000) break;
            if(i % prime[j] == 0){
                //cout << i * prime[j] << endl;
                phi[i * prime[j]] = prime[j] * phi[i];
            }
            else phi[i * prime[j]] = phi[prime[j]] * phi[i];
            if(i % prime[j] == 0) break;
        }
    }
}

int a[10005];
int main()
{
    ios::sync_with_stdio(false);
    memset(phi,0,sizeof(phi));
    init();
    int t,n;
    cin >> t;
    while(t--){
        cin >> n;
        ll ans = 0;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++){
            for(int j = a[i] + 1; j <= 1000000; j++){
                if(phi[j] >= a[i]){
                    ans += 1ll*j;
                    //cout << phi[j] << endl;
                    break;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

1002: 二分+单调队列+01分数规划

原题：https://www.luogu.com.cn/problem/P1419

http://acm.hdu.edu.cn/diy/contest_showproblem.php?cid=36899&pid=1002

不能memset(sum,0,sizeof(sum)),否则会超时

思路：

设所选区间为[L,R]，那么平均值为：x = (mL+...+mR) / (L-R+1)

即mL-x+m(L+1) - x + ...+ mR - x >= 0

先求出m - x的前缀和，那么[L,R]的和为sum[R] - sum[L-1]

又因为小球个数在[a,b]之间，所有a<= R - L + 1 <= b,又因为实际我们求的是sum[i] - sum[q[pl]]

即a + 1 <= i - q[pl] + 1 <= b + 1

即去除q[pl] < i - b的那些点。可以使用单调队列求长度在某一区间的最大和。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
#define _gcd __gcd
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

int mon[100005],n,a,b;
double cz[100005],sum[100005];
int q[100005];
//deque<int>q;

bool check(double x)
{
	//memset(sum,0,sizeof(sum));
	for(int i = 1; i <= n; i++){
		cz[i] = (double)mon[i] - x;
	} 
	sum[0] = 0;
	for(int i = 1; i <= n; i++){
		sum[i] = sum[i - 1] + cz[i];
	}
	int pl = 1,pr = 0;
	for(int i = 1; i <= n; i++){
		if(i >= a){
			while(pl <= pr && sum[q[pr]] > sum[i - a]) pr--;
			pr++;
			q[pr] = i - a;
		}
		while(pl <= pr && q[pl] < i - b) pl++;
		if(pl <= pr && sum[i] - sum[q[pl]] >= 0) return true;
	}
	return false;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n){
    cin >> a >> b;
    for(int i = 1; i <= n; i++) cin >> mon[i];
    double l = -10000,r = 10000,ans;
    ans = l;
    while(r - l > 1e-5){
    	double mid = (l + r) / 2;
    	if(check(mid)){
    		l = mid;
    		ans = mid;
		}
		else r = mid;
		//cout << l << " " << r << endl;
	}
	printf("%.3f\n",ans);
}
    return 0;
}

双端队列做法：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
#define _gcd __gcd
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

int mon[100005],n,a,b;
double cz[100005],sum[100005];
deque<int>q;

bool check(double x)
{
	//memset(sum,0,sizeof(sum));
	sum[0] = 0;
	for(int i = 1; i <= n; i++){
		cz[i] = (double)mon[i] - x;
	} 
	for(int i = 1; i <= n; i++){
		sum[i] = sum[i - 1] + cz[i];
	}
	q.clear(); 
	int p = 0;
	for(int i = a; i <= n; p++,i++){
		while(!q.empty() && sum[p] < sum[q.back()]) q.pop_back();
		q.push_back(p);
		while(!q.empty() && (q.front() < i - b)) q.pop_front();
		if(sum[i] - sum[q.front()] >= 0) return true;
	}
	return false;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n){
    cin >> a >> b;
    for(int i = 1; i <= n; i++) cin >> mon[i];
    double l = -10000,r = 10000,ans;
    ans = l;
    while(r - l > 1e-5){
    	double mid = (l + r) / 2;
    	if(check(mid)){
    		l = mid;
    		ans = mid;
		}
		else r = mid;
		//cout << l << " " << r << endl;
	}
	printf("%.3f\n",ans);
}
    return 0;
}

1006：dfs序+分块

学长代码：https://paste.ubuntu.com/p/dCj2gVT9KP/

思路：

http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1006&cid=36899

#include <iostream> 
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

struct edge{
	int v,next;
	ll val;
}edge[400005];
int head[200005],cnt = 0,t,n,y,d,q;
int st[200005],en[200005],l[200005],r[200005],belong[200005];
ll len[200005],b[200005];
void init()
{
	for(int i = 0; i <= n; i++) head[i] = -1;
}

void add(int u,int v,int d)
{
	edge[cnt].v = v;
	edge[cnt].next = head[u];
	edge[cnt].val = 1ll*d;
	head[u] = cnt++;
}

void dfs(int s,int f)
{
	t++;
	st[s] = t;
	b[t] = len[s];
	for(int i = head[s]; ~i; i = edge[i].next){
		int v = edge[i].v;
		if(v == f) continue;
		len[v] = len[s] + edge[i].val; 
		dfs(v,s);
	}
	en[s] = t;
}

vector<ll>v[200005];
vector<ll>sum[200005];
vector<ll>::iterator it;
void build()
{
	b[1] = 0;
	int block = sqrt(t);
	int num = t / block;
	if(t % block) num++;
	for(int i = 1; i <= num; i++){
		l[i] = (i - 1) * block + 1;
		r[i] = i * block;
		//v[i].push_back(-1);
	}
	r[num] = t;
	for(int i = 1; i <= t; i++){
		belong[i] = (i - 1) / block + 1;
		v[belong[i]].push_back(b[i]);
	}
	for(int i = 1; i <= num; i++){
		sort(v[i].begin(),v[i].end());
	}
	ll temp;
	for(int i = 1; i <= num; i++){
		int k = v[i].size();
		temp = 0;
		for(int j = k - 1; j >= 0; j--){
			temp += v[i][j];
			sum[i].push_back(temp);
		}
	}
}

ll query(int L,int R,ll w,ll k)
{
	ll ans = 0;
	int bl = belong[L];
	int br = belong[R];
	if(bl == br){
		for(int i = L; i <= R; i++){
			if(b[i] - w >= k) ans += b[i] - w;
		}
		return ans;
	}
	ll temp = k + w;
	for(int i = L; i <= r[bl]; i++) if(b[i] - w >= k) ans += b[i] - w;
	for(int i = l[br]; i <= R; i++) if(b[i] - w >= k) ans += b[i] - w;
	for(int i = bl + 1; i < br; i++){
		if(v[i][v[i].size() - 1] < temp) continue;
		it = lower_bound(v[i].begin(),v[i].end(),temp);
		int e = v[i].end() - it;
		if(e == 0) continue;
		ans += sum[i][e - 1] - w * e;
	}
	return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    init();
    cnt = t = 0;
    for(int i = 1; i < n; i++){
    	cin >> y >> d;
    	add(y,i+1,d);
    	add(i+1,y,d);
	}
	dfs(1,0);
	//cout << t << endl;
	build();
	cin >> y;
	int x;
	ll k;
	while(y--){
		cin >> x >> k;
		//cout << st[x] << en[x] << endl;
		ll ans = query(st[x],en[x],len[x],k);
		cout << ans << endl;
	}
    return 0;
}

1009: 最短路

http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1009&cid=36899

思路：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

struct Egde{
    int v,next;
    ll val;
}edge[2000005];

struct node{
    int xb;
    ll val;
    node(int a,ll b){
        xb = a;
        val = b;
    }
    bool operator < (const node &a)const{
        return val > a.val;
    }
};

int head[100005],cnt1,n,m,x;
void add(int u,int v,ll val)
{
    edge[cnt1].v = v;
    edge[cnt1].val = val;
    edge[cnt1].next = head[u];
    head[u] = cnt1++;
}

void init()
{
    for(int i = 0; i <= n; i++) head[i] = -1;
}

int vis[100005];
void dij(int st,ll d[])
{
    for(int i = 0; i <= n; i++) vis[i] = 0,d[i] = ds;
    priority_queue<node>q;
    d[st] = 0;
    q.push(node(st,0));
    while(!q.empty()){
        node s = q.top();
        q.pop();
        int t = s.xb;
        if(vis[t]) continue;
        vis[t] = 1;
        for(int i = head[t]; ~i; i = edge[i].next){
            int p = edge[i].v;
            ll sum = edge[i].val;
            if(vis[p]) continue;
            if(d[p] > s.val + sum){
                d[p] = s.val + sum;
                q.push(node(p,d[p]));
           }
        }
    }
}

int main()
{
    int t,u,v,val;
    ios::sync_with_stdio(false);
    cin >> t;
    while(t--){
        cnt1 = 0;
        ll d1[100005];
        cin >> n >> m >> x;
        init();
        for(int i = 1; i <= n; i++){
            cin >> u;
            for(int j = 1; j <= u; j++){
            	cin >> v;
            	if(j == 1) add(i,v,0);
                else add(i,v,1);
			}
        }
        dij(m,d1);
        if(d1[x] == ds) cout << -1 << endl;
        else cout << d1[x] << endl;
    }
    return 0;
}

1007: 线段树，gcd，更相减损法

原题：https://ac.nowcoder.com/acm/problem/26255?&headNav=acm

http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1007&cid=36899

思路：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
#define _gcd __gcd
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

int a[100005],n,m,opt,x,L,R;
int tree[400005],s_max[400005],g_max[400005];
void push(int xb)
{
	tree[xb] = tree[xb*2] + tree[xb*2+1];
	s_max[xb] = max(s_max[xb*2],s_max[xb*2+1]);
	g_max[xb] = _gcd(g_max[xb*2],g_max[xb*2+1]);
} 

void build(int l,int r,int xb)
{
	if(l == r) {
		tree[xb] = a[l];
		s_max[xb] = abs(a[l]);
		g_max[xb] = abs(a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	build(l,mid,xb*2);
	build(mid+1,r,xb*2+1);
	push(xb);
}

void add(int l,int r,int xb,int k,int val)
{
	if(l == r){
		a[l] += val;
		tree[xb] = a[l];
		s_max[xb] = abs(a[l]);
		g_max[xb] = abs(a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	if(k <= mid) add(l,mid,xb*2,k,val);
	else add(mid+1,r,xb*2+1,k,val);
	push(xb);
}

int sea_max(int l,int r,int xb,int nl,int nr)
{
	if(nl <= l && nr >= r) return abs(s_max[xb]);
	int mid = (l + r) >> 1;
	int l_max = 0,r_max = 0;
	if(nl <= mid) l_max = sea_max(l,mid,xb*2,nl,nr);
	if(nr > mid) r_max = sea_max(mid+1,r,xb*2+1,nl,nr);
	return max(l_max,r_max);
}

int query(int l,int r,int xb,int nl,int nr)
{
	if(nl <= l && nr >= r) return tree[xb];
	int mid = (l + r) >> 1;
	int ans = 0;
	if(nl <= mid) ans += query(l,mid,xb*2,nl,nr);
	if(nr > mid) ans += query(mid+1,r,xb*2+1,nl,nr);
	return ans;
}

int sg_max(int l,int r,int xb,int nl,int nr)
{
	if(nl <= l && nr >= r) return g_max[xb];
	int mid = (l + r) >> 1;
	int l_max = 0,r_max = 0;
	if(nl <= mid) l_max = sg_max(l,mid,xb*2,nl,nr);
	if(nr > mid) r_max = sg_max(mid+1,r,xb*2+1,nl,nr);
	return _gcd(l_max,r_max);
}

int main()
{
    ios::sync_with_stdio(false);
    int t;
    while(cin >> t){
    	while(t--){
    memset(tree,0,sizeof(tree));
    memset(s_max,0,sizeof(tree));
    memset(g_max,0,sizeof(g_max));
    cin >> n >> m;
    a[0] = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = n; i >= 1; i--) a[i] = a[i] - a[i - 1];
	build(1,n,1); 
	while(m--){
	cin >> opt >> L >> R;
	if(opt == 1){
		cin >> x;
		add(1,n,1,L,x);
		if(R < n) add(1,n,1,R+1,-x);
	}
	if(opt == 2){
		if(L == R){
			cout << 0 << endl;
			continue;
		}
		int ans = sea_max(1,n,1,L + 1,R);
		cout << ans << endl;
	}
	if(opt == 3){
	    int ans = query(1,n,1,1,L);
		if(L != R) ans = _gcd(ans,sg_max(1,n,1,L+1,R));
	    cout << ans << endl;
	}
  }
 }
}
    return 0;
}