A - Always Online
Unsolved.
B - Beautiful Now
Solved.
题意：
给出一个n, k 每次可以将n这个数字上的某两位交换，最多交换k次，求交换后的最大和最小值
思路：
很明显有一种思路，对于最小值，尽可能把小的放前面， 对于最大值，尽可能把打的放前面。但是如果有多个最小数字或者最大数字会无法得出放哪个好，因此BFS一下即可
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + ; struct node{
int num, idx, step;
node(){}
node(int num, int idx, int step) :num(num), idx(idx), step(step){}
}; int n, k;
int cnt;
int arr[maxn]; int BFS1()
{
queue<node>q;
q.push(node(n, cnt, ));
int ans = INF;
while(!q.empty())
{
node now = q.front();
q.pop();
ans = min(ans, now.num);
if(now.step == k) continue;
if(now.idx == ) continue;
int tmp = now.num;
cnt = ;
while(tmp)
{
arr[++cnt] = tmp % ;
tmp /= ;
}
int Min = now.idx;
for(int i = now.idx - ; i >= ; --i)
{
if(arr[i] == arr[now.idx]) continue;
if(arr[i] == && now.idx == cnt) continue;
if(arr[i] < arr[Min]) Min = i;
}
if(Min == now.idx)
{
q.push(node(now.num, now.idx - , now.step));
}
else
{
for(int i = now.idx - ; i >= ; --i)
{
if(arr[i] == arr[Min])
{
swap(arr[i], arr[now.idx]);
tmp = ;
for(int j = cnt; j >= ; --j)
{
tmp = tmp * + arr[j];
}
q.push(node(tmp, now.idx - , now.step + ));
swap(arr[i], arr[now.idx]);
}
}
}
}
return ans;
} int BFS2()
{
queue<node>q;
q.push(node(n, cnt, ));
int ans = -INF;
while(!q.empty())
{
node now = q.front();
q.pop();
ans = max(ans, now.num);
if(now.step == k) continue;
if(now.idx == ) continue;
int tmp = now.num;
cnt = ;
while(tmp)
{
arr[++cnt] = tmp % ;
tmp /= ;
}
int Max = now.idx;
for(int i = now.idx - ; i >= ; --i)
{
if(arr[i] == arr[now.idx]) continue;
if(arr[i] > arr[Max]) Max = i;
}
if(Max == now.idx)
{
q.push(node(now.num, now.idx - , now.step));
}
else
{
for(int i = now.idx - ; i >= ; --i)
{
if(arr[i] == arr[Max])
{
swap(arr[i], arr[now.idx]);
tmp = ;
for(int j = cnt; j >= ; --j)
{
tmp = tmp * + arr[j];
}
q.push(node(tmp, now.idx - , now.step + ));
swap(arr[i], arr[now.idx]);
}
}
}
}
return ans;
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n ,&k);
int tmp = n;
cnt = ;
while(tmp)
{
cnt++;
tmp /= ;
}
k = min(k, cnt - );
int ans1 = BFS1();
int ans2 = BFS2();
printf("%d %d\n", ans1, ans2);
}
return ;
}
C - Call It What You Want
Unsolved.
D - Daylight
Unsolved.
E - Everything Has Changed
Solved.
题意：
求多个圆的周长并
思路：
对于不想交和内含的直接continue，相切的直接相加。对于相交的可以减去大圆上的弧长，加上小圆的弧长
#include<bits/stdc++.h> using namespace std; const double PI = acos(-1.0);
const double eps = 1e-; int sgn(double x)
{
if(fabs(x) < eps) return ;
else return x > ? : -;
} struct Point{
double x, y;
Point(){}
Point(double _x, double _y)
{
x = _x;
y = _y;
} double distance(Point p)
{
return hypot(x - p.x, y - p.y);
}
}P; int n;
double R, r; int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d %lf", &n, &R);
double ans = * R * PI;
for(int i = ; i <= n; ++i)
{
scanf("%lf %lf %lf", &P.x, &P.y, &r);
double dis = P.distance(Point(0.0, 0.0));
if(sgn(dis - (r + R)) >= ) continue;
else if(sgn(dis - (R - r)) < ) continue;
else if(sgn(dis - (R - r)) == )
{
ans += * PI * r;
continue;
}
double arc1 = (R * R + dis * dis - r * r) / (2.0 * R * dis);
arc1 = * acos(arc1);
double arc2 = (r * r + dis * dis - R * R) / (2.0 * r * dis);
arc2 = * acos(arc2);
ans -= R * arc1;
ans += r * arc2;
}
printf("%.10f\n", ans);
}
return ;
}
F - Fireflies
Unsolved.
G - Glad You Came
Upsolved.
题意：
m个区间操作，每次给$[L, R]区间内小于v 的数变为v$
思路：
线段树，维护最大最小值+剪枝，因为数据随机才可以这样做。
#include <bits/stdc++.h>
using namespace std; #define N 5000010
#define M 100010
#define ui unsigned int
#define ll long long
int t, n, m;
ui x, y, z, w;
ui f[N << ];
ui MOD = (ui) << ; ui rng61()
{
x = x ^ (x << );
x = x ^ (x >> );
x = x ^ (x << );
x = x ^ (x >> );
w = x ^ y ^ z;
x = y;
y = z;
z = w;
return z;
} struct SEG
{
ui lazy[M << ], Max[M << ], Min[M << ];
void Init()
{
memset(lazy, , sizeof lazy);
memset(Max, , sizeof Max);
memset(Min, , sizeof Min);
}
void pushup(int id)
{
Max[id] = max(Max[id << ], Max[id << | ]);
Min[id] = min(Min[id << ], Min[id << | ]);
}
void pushdown(int id)
{
if (!lazy[id]) return;
lazy[id << ] = lazy[id];
Max[id << ] = lazy[id];
Min[id << ] = lazy[id];
lazy[id << | ] = lazy[id];
Max[id << | ] = lazy[id];
Min[id << | ] = lazy[id];
lazy[id] = ;
}
void update(int id, int l, int r, int ql, int qr, ui val)
{
if (Min[id] >= val) return;
if (l >= ql && r <= qr && Max[id] < val)
{
lazy[id] = Max[id] = val;
return;
}
pushdown(id);
int mid = (l + r) >> ;
if (ql <= mid) update(id << , l, mid, ql, qr, val);
if (qr > mid) update(id << | , mid + , r, ql, qr, val);
pushup(id);
}
int query(int id, int l, int r, int pos)
{
if (l == r) return Max[id];
pushdown(id);
int mid = (l + r) >> ;
if (pos <= mid) return query(id << , l, mid, pos);
else return query(id << | , mid + , r, pos);
}
}seg; int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d%u%u%u", &n, &m, &x, &y, &z);
for (int i = ; i <= * m; ++i) f[i] = rng61();
seg.Init();
for (int i = , l, r, v; i <= m; ++i)
{
l = f[ * i - ] % n + ;
r = f[ * i - ] % n + ;
v = f[ * i] % MOD;
if (l > r) swap(l, r);
seg.update(, , n, l, r, v);
}
ll res = ;
for (int i = ; i <= n; ++i)
res ^= (ll)seg.query(, , n, i) * (ll)i;
printf("%lld\n", res);
}
return ;
}
H - Hills And Valleys
Upsolved,
题意：
给出一个长为n的数字串，每一位范围是$[0, 9]$，可以翻转其中一段，使得最长非下降子序列最长
思路：
也就是说 可以存在这样一段
$0, 1, 2....., x, (x - 1) , y, (y - 1).... x, y + 1, y + 2..$
我们知道，如果不可以翻转，求最长上升子序列的话，我们可以将原串 和模式串$0123456789$ 求最长公共子序列
那么翻转的话，我们通过枚举翻转的区间$C(2, 10)$ 构造出上述的模式串，再求最长公共子序列
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define INF 0x3f3f3f3f
int t, n, m, a[N], b[];
int dp[N][], tl[N][], tr[N][], res, l, r, ql, qr; void solve()
{
for (int i = ; i <= m; ++i) dp[][i] = , tl[][i] = -, tr[][i] = -;
for (int i = ; i <= n; ++i) for (int j = ; j <= m; ++j)
{
dp[i][j] = dp[i - ][j];
tl[i][j] = tl[i - ][j];
tr[i][j] = tr[i - ][j];
if (a[i] == b[j])
{
++dp[i][j];
if (j == ql && tl[i][j] == -) tl[i][j] = i;
if (j == qr) tr[i][j] = i;
}
if (j > && dp[i][j - ] > dp[i][j])
{
dp[i][j] = dp[i][j - ];
tl[i][j] = tl[i][j - ];
tr[i][j] = tr[i][j - ];
}
}
if (ql == && qr == )
{
res = dp[n][m];
l = ;
r = ;
}
else if (dp[n][m] > res && tl[n][m] != - && tr[n][m] != -)
{
res = dp[n][m];
l = tl[n][m];
r = tr[n][m];
}
} int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
res = , l = , r = ;
for (int i = ; i <= n; ++i) scanf("%1d", a + i);
for (int i = ; i <= ; ++i) b[i] = i - ; m = ; ql = , qr = ;
solve();
for (int i = ; i < m; ++i) for (int j = i + ; j <= ; ++j)
{
m = ;
for (int pos = ; pos <= i; ++pos) b[++m] = pos - ;
ql = m + ;
for (int pos = j; pos >= i; --pos) b[++m] = pos - ;
qr = m;
for (int pos = j; pos <= ; ++pos) b[++m] = pos - ;
solve();
//for (int i = 1; i <= m; ++i) printf("%d%c", b[i], " \n"[i == m]);
}
printf("%d %d %d\n", res, l, r);
}
return ;
}
I - Innocence
Unsolved.
J - Just So You Know
Unsolved.
K - Kaleidoscope
Unsolved.
L - Lost In The Echo
Unsolved.