text-2020
http://acm.hdu.edu.cn/diy/contest_show.php?cid=36899
1010-我！是！签！到！题！：BFS
思路：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：欧拉函数
思路：根据题意可看出，我们要找出某个最小的数去满足获取全部香蕉，又因为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分数规划
不能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序+分块
思路：
#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: 最短路
思路：
#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，更相减损法
思路：
#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;
} 
