2021.10.06
T1
Description
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
小葱同学最近醉心于动态规划的研究，他苦学百年，已经牢牢掌握了最长上升子序列的知识。小葱对于这种单调不减的序列非常着迷，于是他灵机一动，挥笔写下了一个数 \(\)，现在小葱同学希望找到一个小于等于 \(\) 的最大的数，使得这个数的各个数位是单调不减的。求这个数。
Solution
手模几组样例发现答案就是第一个下降位置的前一位减 1 ，然后将其后面的位置都赋为 9.
Code
/*
* @Author: smyslenny
* @Date: 2021.10.
* @Title:
* @Main idea:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#define ll long long
#define INF 0x3f3f3f3f
#define orz cout<<"LKP AK IOI\n"
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(a):(b)
using namespace std;
const int mod=998244353;
const int M=1e6+5;
int x;
int read()
{
int x=0,y=1;
char c=getchar();
while(c<'0' || c>'9') {if(c=='-') y=0;c=getchar();}
while(c>='0' && c<='9') { x=x*10+(c^48);c=getchar();}
return y?x:-x;
}
namespace substack1{
bool check(int x)
{
int las=x%10;
x/=10;
while(x)
{
if(x%10>las) return false;
las=x%10;
x/=10;
}
return true;
}
void main()
{
x=read();
for(int i=x;i>=0;i--)
{
if(check(i))
{
printf("%d\n",i);
return;
}
}
}
}
namespace substack2{
char s[M];
int sz[M],pos;
void main()
{
scanf("%s",s+1);
int len=strlen(s+1);
if(len==1 && s[1]=='0')
{
printf("0\n");
return;
}
for(int i=1;i<=len;i++)
sz[i]=s[i]-'0';
for(int i=len;i>=1;i--)
if(sz[i]<sz[i-1]) sz[i]=9,sz[i-1]--;
for(int i=1;i<=len;i++)
if(sz[i])
{
pos=i;
break;
}
for(int i=pos;i<=len;i++)
{
if(sz[i-1]==9) printf("9"),sz[i]=9;
else printf("%d",sz[i]);
}
printf("\n");
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("zhengjie.out","w",stdout);
substack2::main();
return 0;
}
T2
Description
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
小葱同学自幼学习乘法和加法，并且小葱同学意识到，正是因为有了加法和乘法，才能够计算 \(1 + 1 = 2\) 和 \(1 × 1 = 1\) 这种高深的问题。现在小葱给你个数 \(_1, _2, ⋯ , _\)，求下列式子的值：
\(\sum\limits_{l=1}^n \sum\limits_{r=l}^n \sum\limits_{i=l}^r \sum\limits_{j=i+1}^r _ \times _\)
Solution
其实80分还是比较好想的，但是错了一个小地方，沦为与暴力同分。
我们去找每个逆序对能够做出的贡献区间，一个个算比较麻烦，可以考虑容斥，用总的区间减去 \(i\) 在 \(j\) 不在的区间，\(j\) 在 \(i\) 不在的区间，然后加上两者都不在的区间，因为减了两次。
复杂度的瓶颈主要在于求逆序对，普通的求法是 \(n^2\) 的，可以用树状数组求逆序对。计算贡献。
Code
/*
* @Author: smyslenny
* @Date: 2021.10.
* @Title:
* @Main idea:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#define int long long
#define INF 0x3f3f3f3f
#define orz cout<<"LKP AK IOI\n"
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(a):(b)
using namespace std;
const int mod=1e12+7;
const int M=4e5+5;
int n,a[M],Ans;
int read()
{
int x=0,y=1;
char c=getchar();
while(c<'0' || c>'9') {if(c=='-') y=0;c=getchar();}
while(c>='0' && c<='9') { x=x*10+(c^48);c=getchar();}
return y?x:-x;
}
namespace substack1{
void main()
{
for(int l=1;l<=n;l++)
for(int r=l;r<=n;r++)
for(int i=l;i<=r;i++)
for(int j=i+1;j<=r;j++)
if(a[j]<a[i])
Ans=(Ans+a[i]*a[j]%mod)%mod;
printf("%lld\n",Ans);
}
}
namespace substack2{
int get_(int x)
{
return ((x-1)*x/2)%mod;
}
void main()
{
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[j]<a[i])
Ans=(Ans+a[j]*a[i]%mod*(get_(n)-get_(j-1)-get_(n-i)+get_(j-i-1))%mod)%mod;
printf("%lld\n",Ans);
}
}
signed main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
// if(n<=100) substack1::main();
// else
substack2::main();
return 0;
}
T3
Description
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
小葱同学现在抵挡咕星人的进攻。咕星人的进攻非常猛烈，以至于小葱同学不得不进行防守。为了更好地防守咕星人的进攻，小葱同学制作了面盾牌，其中第面盾牌的形状是左下角在 (, ) 右上角在 (, ) 的矩形。现在小葱将这面盾牌组合在了一起，并且只有当这面盾牌组成了一个漂亮的矩形时，小葱才能够抵挡咕星人的进攻。一个漂亮的矩形指的是盾牌不遗漏的覆盖了这个矩形内的每一个位置，并且每一个位置最多只被一个盾牌所覆盖（边界相交不算覆盖多次）。
现在给定你这 面盾牌，你需要帮助小葱同学判断这 面盾牌是否组成了一个漂 亮的矩形。
Solution
发现一个完美的矩形除了四个顶点可能会出现1个点，其他的地方都会出现2或4个点。
Code
/*
@Authour: smyslenny
@Date: 2021.10.07
@Title:
@Main idea:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <map>
#define orz cout<<"LKP AK IOI\n"
#define ll long long
#define INF 0x3f3f3f3f
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)<(b)?(a):(b)
#define ABS(a) (a)>=0?(a):(-a)
using namespace std;
const int M=5e4+5;
int T,n;
inline int read()
{
register int x=0,y=1;
register char c=getchar();
while(!isdigit(c)) {if(c=='-') y=0;c=getchar();}
while(isdigit(c)) {x=x*10+(c^48);c=getchar();}
return y?x:-x;
}
int js,L,R,U,D,sum,a[M],b[M],c[M],d[M];
map<int,map<int,int > > num;
void init()
{
num.clear();
R=D=-INF;
L=U=INF;
sum=js=0;
}
bool solve()
{
for(int i=1;i<=n;i++)
{
L=MIN(L,MIN(b[i],d[i]));
R=MAX(R,MAX(b[i],d[i]));
U=MIN(U,MIN(a[i],c[i]));
D=MAX(D,MAX(a[i],c[i]));
sum+=abs(c[i]-a[i])*abs(b[i]-d[i]);
}
if(sum!=(R-L)*(D-U))
return false;
for(int i=1;i<=n;i++)
{
num[a[i]][b[i]]++;
num[a[i]][d[i]]++;
num[c[i]][b[i]]++;
num[c[i]][d[i]]++;
if(num[a[i]][b[i]]==2 || num[a[i]][b[i]]==4) js--;
if(num[a[i]][d[i]]==2 || num[a[i]][d[i]]==4) js--;
if(num[c[i]][b[i]]==2 || num[c[i]][b[i]]==4) js--;
if(num[c[i]][d[i]]==2 || num[c[i]][d[i]]==4) js--;
if(num[a[i]][b[i]]!=2 && num[a[i]][b[i]]!=4) js++;
if(num[a[i]][d[i]]!=2 && num[a[i]][d[i]]!=4) js++;
if(num[c[i]][b[i]]!=2 && num[c[i]][b[i]]!=4) js++;
if(num[c[i]][d[i]]!=2 && num[c[i]][d[i]]!=4) js++;
}
return js==4;
}
int main()
{
T=read();
while(T--)
{
init();
n=read();
for(int i=1;i<=n;i++)
a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
if(solve()) printf("Perfect\n");
else printf("Guguwansui\n");
}
system("pause");
return 0;
}
/*
2
5
3 1 4 2
1 1 3 3
2 3 3 4
3 2 4 4
1 3 2 4
4
2 2 4 4
1 1 3 3
3 1 4 2
1 3 2 4
*/