2020-2021 “Orz Panda” Cup Programming Contest
A. Accordion Artist And Orz Pandas
题意
给定\(n\)个相邻的矩形，矩形的宽和高给定，问最大的子矩形面积
分析
单调栈板题，维护出每个矩形左边第一个比他低的点和右边第一个比它低的点，两点距离就是宽，高就是当前矩形的高，维护宽X高的最大值即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll rd(){
ll x;
scanf("%lld",&x);
return x;
}
int main(){
int n = rd();
vector<ll> h(n + 1),w(n + 1);
vector<ll> sum(n + 1);
vector<int> lpos(n + 1),rpos(n + 1);
for(int i = 1;i <= n;i++){
h[i] = rd();
w[i] = rd();
sum[i] = sum[i - 1] + w[i];
}
stack<int> st;
for(int i = 1;i <= n;i++){
while(!st.empty() && h[st.top()] > h[i]) {
rpos[st.top()] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()) {
rpos[st.top()] = n + 1;
st.pop();
}
for(int i = n;i >= 1;i--){
while(!st.empty() && h[st.top()] > h[i]) {
lpos[st.top()] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()){
lpos[st.top()] = 0;
st.pop();
}
ll ans = 0;
for(int i = 1;i <= n;i++){
ll W = sum[rpos[i] - 1] - sum[lpos[i]];
ans = max(ans,W * h[i]);
}
cout << ans;
}
C. Closestools of Orz Pandas
题意
模拟题
给定\(n\)个房间，定义i,j号房间距离\(|i - j|\)
操作1：选择一个空房间进入，要求该空房间得到的和其他非空房间生成的距离排序后字典序最小
操作2：将第x次操作的房间变为空房间
分析
贪心策略：
把空房间看成线段，每次找到最长的线段，取最长线段的中点。
通常维护线段可以用set实现。再用另一个线段维护非空房间，可以快速得到左右点位置。
代码
#include<bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;
int rd(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9') {
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
struct Seg{
int l,r; //[l,r]
Seg(int _l = 0,int _r = 0){
l = _l;
r = _r;
}
int d() const {
return (r - l) / 2 + 1;
}
bool operator < (const Seg& b) const{
int d1 = d();
int d2 = b.d();
return (d1 > d2) || (d1 == d2 && l < b.l);
}
};
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
set<Seg> s;
s.insert(Seg(1,n));
set<int> st;
vector<int> v(m + 1);
for(re int i = 1;i <= m;i++){
int op = rd();
if(op == 1) {
auto best = s.begin();
int bestd = best -> d();
if(!st.empty() && *st.begin() > bestd) {
best = s.lower_bound(Seg(1,*st.begin() - 1));
bestd = (*st.begin() - 1) / 2;
}
if(!st.empty() && n - *st.rbegin() > bestd) {
best = s.lower_bound(Seg(*st.rbegin() + 1,n));
bestd = (n - *st.rbegin()) / 2;
}
if(st.empty())
best = s.begin();
int pos = best -> l + bestd - 1;
if(best -> l == 1)
pos = 1;
else if(best -> r == n)
pos = n;
printf("%d\n",pos);
v[i] = pos;
st.insert(pos);
Seg L = Seg(best -> l,pos - 1);
Seg R = Seg(pos + 1,best -> r);
s.erase(best);
if(L.l <= L.r)
s.insert(L);
if(R.l <= R.r)
s.insert(R);
}
else {
int x = rd();
int pos = v[x];
auto it = st.lower_bound(pos);
auto itt = it;
int L = (it != st.begin() ? *(--it) + 1 : 1);
itt++;
int R = (itt != st.end() ? *itt - 1 : n);
if(L <= pos - 1)
s.erase(Seg(L,pos - 1));
if(pos + 1 <= R)
s.erase(Seg(pos + 1,R));
s.insert(Seg(L,R));
st.erase(pos);
}
}
}
}
D. Data Structure Master and Orz Pandas
题意
大概意思就是求期望(如有不对的地方请指正)
对一颗树中的某点，找到根到这个点的路径把这条路径上的边都变成实边（LCT中，某个点的儿子中只能连一条实边），类似LCT的access操作
求稳态下拉一个点，边从虚边变为实边的期望次数
分析
考虑答案组成，枚举每个点，那么这个点到路径上所有点被修改的期望次数的和就是答案（期望的可加性）
即
\[ans = \frac{1}{n}\sum_u \sum_{v是u到root的路径上的点} E(v和fa的边不是实边) \]考虑\(E\),显然只和\(v\)和\(fa_v\)有关，简单推导（直觉）就可以得到\(E = 1 - \frac{siz(v)}{siz(fa_v) - 1}\)
于是变换求和顺序即可得
\[ans = \frac{1}{n} \sum_u siz(u) (1 - \frac{siz(u)}{siz(fa_u) - 1}) \]dfs即可
代码
#include<bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;
int rd(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9') {
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
const int maxn = 1e5 + 5;
const int MOD = 998244353;
ll ksm(ll a,ll b = MOD - 2,ll m = MOD){
ll base = a;
ll ans = 1;
while(b){
if(b & 1) ans *= base,ans %= MOD;
base *= base;
base %= MOD;
b >>= 1;
}
return ans;
}
int Fa[maxn];
int siz[maxn];
vector<int> e[maxn];
int ans;
void dfs(int u,int fa){
Fa[u] = fa;
siz[u] = 1;
for(auto v:e[u]) {
dfs(v,u);
siz[u] += siz[v];
}
}
int main(){
int n = rd();
for(int i = 2;i <= n;i++){
int x = rd();
e[x].push_back(i);
}
dfs(1,0);
for(int u = 2;u <= n;u++){
ans += (ll)siz[u] * (1 - (ll)siz[u] * ksm(siz[Fa[u]] - 1 + MOD) % MOD + MOD) % MOD,ans %= MOD;
}
ans = (ll) ans * ksm(n) % MOD;
cout << ans;
}
E. Encryption of Orz Pandas
题意
经过转化可以把问题变为：
给定长度\(n\)的01序列，对序列做k次前缀和，求k次前缀和后的序列
\(n \leq 1e5\)
分析
做k次前缀和可以用生成函数看成乘上\((1 + x+ x^2...+x^n)^k\)
即若有序列\((a_0,a_1...a_n)\)，那么k次前缀和后的\(a_i = [x^i](a_0 + a_1 ...+a_n) \times (1+x+x^2...x^n)^k\)
做法可以用题解写的泰勒展开后转化为组合数再FFT，复杂度\(O(nlogn)\)
不过我看不懂，比较朴素的想法是对\(FFT\)做快速幂复杂度\(O(nlognlogk)\) 考虑到时限5s可以冲一冲
我觉得FFT调试起来有点麻烦，事实上当时没调出来，赛后发现用NTT即可，01序列做1次不会爆模数
代码
#include<bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;
ll rd(){
ll x = 0;
char ch = getchar();
while(ch < '0' || ch > '9') {
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
const int maxn = 2e5 + 5;
class NTTClass{
public:
static const int MAXL=22;
static const int MAXN=1<<MAXL;
static const int root=3;
static const int MOD=998244353;
int rev[MAXN];
int fast_pow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%MOD;
a=1ll*a*a%MOD;
b>>=1;
}
return ans;
}
void transform(int n,int *t,int typ){
for(int i=0;i<n;i++)
if(i<rev[i])swap(t[i],t[rev[i]]);
for(int step=1;step<n;step<<=1){
int gn=fast_pow(root,(MOD-1)/(step<<1));
for(int i=0;i<n;i+=(step<<1)){
int g=1;
for(int j=0;j<step;j++,g=1ll*g*gn%MOD){
int x=t[i+j],y=1ll*g*t[i+j+step]%MOD;
t[i+j]=(x+y)%MOD;
t[i+j+step]=(x-y+MOD)%MOD;
}
}
}
if(typ==1)return;
for(int i=1;i<n/2;i++)swap(t[i],t[n-i]);
int inv=fast_pow(n,MOD-2);
for(int i=0;i<n;i++)t[i]=1ll*t[i]*inv%MOD;
}
void ntt(int p,int *A,int *B,int *C){
transform(p,A,1);
transform(p,B,1);
for(int i=0;i<p;i++)C[i]=1ll*A[i]*B[i]%MOD;
transform(p,C,-1);
}
void mul(int *A,int *B,int *C,int n,int m) {
int p=1,l=0;
while(p<=n+m)p<<=1,l++;
//printf("n = %d, m = %d\n",n,m);
for (int i=n+1;i<p;i++) A[i] = 0;
for (int i=m+1;i<p;i++) B[i] = 0;
//for (int i=0;i<p;i++) printf("%d ",A[i]);puts("");
//for (int i=0;i<p;i++) printf("%d ",B[i]);puts("");
for(int i=0;i<p;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
ntt(p,A,B,C);
//puts("C:");for (int i=0;i<p;i++) printf("%d ",C[i]);puts("");
}
}NTT;
int _[maxn << 1],f[maxn << 1];
int ans[maxn << 1],p[maxn << 1],ttt[maxn << 1];
int n,m,mm;
inline void ksm(int *a,ll b){
ans[0] = 1;
for(re int i = 1;i < n;i++)
ans[i] = 0;
while(b){
if(b & 1){
for(re int i = 0;i < n;i++)
p[i] = a[i];
NTT.mul(ans,a,_,n,n);
for(re int i = 0;i < n;i++)
a[i] = p[i],ans[i] = (_[i] & 1 ? 1 : 0);
}
for(re int i = 0;i < n;i++)
p[i] = a[i];
NTT.mul(a,p,_,n,n);
for(re int i = 0;i < n;i++)
a[i] = (_[i] & 1 ? 1 : 0);
//for(re int i = 0;i <= mm;i++) {
// int tmp = (int)(ans[i].x / n + 0.49);
// if(tmp & 1) ans[i].x = 1;
// else ans[i].x = 0;
//}
b >>= 1;
}
}
int main(){
n = rd();
mm = n;
m = n;
ll k = rd();
int cnt = 0;
int M = mm;
while(M) M /= 2,cnt++;
if((1ll << cnt) != mm) cnt++;
k = (k - 1) % (1 << cnt);
k++;
vector<ll> v(mm);
vector<ll> res(mm);
for(int i = 0;i < mm;i++)
v[i] = rd();
for(int i = 0;i < n;i++)
f[i] = 1;
ksm(f,k);
//for(int i = 0;i <= mm;i++)
// printf("%d ",ans[i]);
for(int i = 0;i <= 17;i++){
for(re int j = 0;j < mm;j++){
int tttt = ((v[j] >> i) & 1);
ttt[j] = ans[j];
f[j] = tttt;
}
for(int j = mm;j < n;j++){
ttt[j] = f[j] = 0;
}
/*
if(i == 2) for(int j = 0;j < n;j++){
cout << ttt[j].x << ' ' << f[j].x << '\n';
}*/
NTT.mul(f,ttt,_,n,n);
for(re int j = 0;j < mm;j++){
int ok = _[j] & 1 ? 1 : 0;
//if(ok) cout << "i = " << i << "j = " << j << '\n';
if(ok) res[j] |= (1ll << i);
}
}
for(int i = 0;i < mm;i++)
if(i) putchar(' '),cout << res[i];
else cout << res[i];
}
H. Hamming Code and Orz Pandas
模拟题，因为我没有参与此题，所以无法提供解释
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll rd(){
ll x = 0;
int 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 - '0';
ch = getchar();
}
return x * f;
}
int k;
string d;
vector<int>a;
vector<int>have[20];
void init()
{
int num=1;
a.push_back(0);
for(int i=1;i<=17;i++){
a.push_back(num);
num=num*2;
}
int p=1;
for(int i=3;i<=1024*64*2;i++){
p=i;
for(int j=16;j>=1;j--){
if(i==a[j]){
p=0;
break;
}
}
if(p==0)continue;
int hh=0;
while(p){
for(int j=17;j>=1;j--){
hh=0;
while(p>=a[j]){
p-=a[j];
hh=1;
}
if(hh)have[j].push_back(i);
if(p==0)break;
}
}
}
}
int main()
{
init();
while(~scanf("%d",&k)){
cin>>d;
int num=0;
for(int i=0;i<d.size();i++){
num=num^d[i];
}
if(num==0){
int wa=0;
for(int i=1;i<=k;i++){
int pos=0;
//cout<<i<<":"<<endl;
for(auto x:have[i]){
if(x>=a[k+1])break;
//cout<<x<<endl;
pos=pos^d[x];
}
if(pos!=d[a[i]]){
wa=1;
break;
}
}
if(wa){
printf("broken\n");
}else{
printf("good\n");
}
}else{
vector<int>ans;
for(int i=1;i<=k;i++){
int pos=0;
for(auto x:have[i]){
if(x>=a[k+1])break;
pos=pos^d[x];
}
if(pos!=d[a[i]]){
ans.push_back(a[i]);
}
}
//cout<<ans.size()<<endl;
if(ans.size()==1){
printf("d(%d) is changed\n",ans[0]);
}else{
int sum=0;
for(auto x:ans){
sum+=x;
}
printf("d(%d) is changed\n",sum);
}
}
}
}
/*
4
1011101110111011
4
1011101110111010
4
1011101110111110
*/
I. Irregular Shape of Orz Pandas
题意
顺序给出点，求多边形面积
\[3 \leq n \leq 1e3\\ -1e9 \leq x,y \leq 1e9 \]分析
一开始用double算，发现爆了，因为给的是整点，所以直接用__int128，事实上longlong即可，最后除以二可以人为加小数 这题花了很长时间，实在是不应该
代码
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
ll rd(){
ll x = 0;
int 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 - '0';
ch = getchar();
}
return x * f;
}
void Put(ll x){
if(x == 0) return;
if(x < 10) {
putchar(x + '0');
return;
}
Put(x / 10);
putchar(x % 10 + '0');
}
struct Point{
ll x;
ll y;
Point(){}
Point(ll _x,ll _y):x(_x),y(_y){}
};
ll operator ^ (const Point &a,const Point &b){
return a.x * b.y - a.y * b.x;
}
Point operator - (const Point &a,const Point &b){
return Point(a.x - b.x,a.y - b.y);
}
struct Pol{
int n;
Point p[1005];
void input(int _n){
n = _n;
for(int i = 0;i < n;i++){
p[i].x = rd();
p[i].y = rd();
}
}
ll getarea(){
ll sum = 0;
for(int i = 0;i < n;i++){
sum += ((p[i]) ^ (p[(i + 1) % n]));
}
return sum;
}
};
int main(){
int n;
while(~scanf("%d",&n)){
Pol poly;
poly.input(n);
ll tmp = poly.getarea();
if(tmp < 0) tmp *= -1;
if(tmp % 2 == 1) {
Put(tmp / 2);
putchar('.');
putchar('5');
putchar('0');
}
else {
Put(tmp / 2);
putchar('.');
putchar('0');
putchar('0');
}
puts("");
}
}