寒假学习计划
比赛链接
[A] Convolution
题意
给出一个整数序列,求\sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_{i}a_{j}},答案对998244353取模
题解
2^{xy}=\sqrt{2}^{(x+y)^2-x^2-y^2}
根据上面的式子形式,做NTT
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <complex>
#include <algorithm>
#define IL inline
#define LL long long
#define ULL unsigned LL
#define _BS 1048576
char _bf[_BS];
char *__p1=_bf,*__p2=_bf;
#define _IO char *_p1=__p1,*_p2=__p2;
#define _OI __p1=_p1,__p2=_p2;
#define GC (_p1==_p2&&(_p2=(_p1=_bf)+fread(_bf,1,_BS,stdin),_p1==_p2)?EOF:*_p1++)
#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)
#define _G1(_1) int _1;sc(_1)
#define _G2(_1,_2) int _1,_2;sc(_1)sc(_2)
#define _G3(_1,_2,_3) int _1,_2,_3;sc(_1)sc(_2)sc(_3)
#define _gG(_1,_2,_3,_get, ...) _get
#define get(...) _gG(__VA_ARGS__,_G3,_G2,_G1, ...)(__VA_ARGS__)
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FD(i,l,r) for(int i=(l);i<=(r);++i)
#define MIN(a, b) ((a)<(b)?(a):(b))
#define MAX(a, b) ((a)>(b)?(a):(b))
template<class T>
void UPRT(const T _){if(_>=10)UPRT(_/10);PC(_%10+48);}
#define UPL(_) UPRT(_),PC(10)
// 【注意】如果PRT里面不是UPRT<unsigned long long>(-(ULL)_)而是直接UPRT(-_)则会出问题。比如INT_MIN和LLONG_MIN就打不出来。
template<class T>
void PRT(const T _){if(_<0){PC(45),UPRT<ULL>(-(ULL)_);return;}if(_>=10)PRT(_/10);PC(_%10+48);}
#define PL(_) PRT(_),PC(10)
#define CON constexpr
#define SW(a,b) ({auto _t=a; a=b; b=_t;})
CON LL G(3), MOD(998244353), S2(116195171), S2I(557219762);
CON LL MN(1e6+7);
template <typename T>
T QP(T __a, T __b)
{
T __ret = 1;
while (__b)
{
if (__b&1)
__ret = (__ret*__a)%MOD;
__a *= __a,
__a %= MOD,
__b >>= 1;
}
return __ret;
}
int re[MN];
void pre(int n) // 【千万不要忘记！】
{
int bn = 0;
while ((1<<bn)<n) ++bn;
F(i, 0, n)
re[i] = (re[i>>1]>>1) | ((i&1)<<(bn-1));
}
void ntt(LL *a, int n, int sg) // sg=1:正, sg=-1:逆
{
F(i, 0, n) if (i < re[i]) SW(a[i], a[re[i]]);
for (int m=1; m<n; m<<=1)
{
LL g = QP(G, (MOD-1) / (m<<1));
for (int i=0; i<n; i+=m<<1)
{
LL t = 1;
for (int j=0; j<m; ++j, t=t*g%MOD)
{
LL x = a[i+j], y = t*a[i+j+m]%MOD;
a[i+j] = (x+y) % MOD, a[i+j+m] = (x-y+MOD) % MOD;
}
}
}
if (sg<0)
{
LL nn = QP((LL)n, MOD-2);
std::reverse(a+1, a+n);
F(i, 0, n)
(a[i] *= nn) %= MOD;
}
}
LL a[MN], c[MN];
int main()
{
_IO
get(n)
int mx = 0, x;
F(i, 0, n)
{
sc(x)
mx = MAX(mx, x);
(a[x] += QP(S2I, (LL)x*x)) %= MOD;
}
mx = mx * 2 + 1;
int len = 1;
while (len <= mx) len <<= 1;
pre(len); // 【千万不要忘记！】
ntt(a, len, 1);
F(i, 0, len)
c[i] = a[i] * a[i] % MOD;
ntt(c, len, -1);
LL ans = 0;
F(i, 0, len)
(ans += c[i] * QP(S2, (LL)i*i)) %= MOD;
PL(ans);
#ifdef _KEVIN
system("pause");
#endif
return 0;
}
[C] 酒馆战棋
题意
题目背景:酒馆战棋
对面随从身材全为无限大且不会攻击,我方随从身材为1-1,只有普通和剧毒两种,从左至右依次攻击一轮.
给出对面普通,圣盾,嘲讽,圣盾嘲讽的随从个数,我方带剧毒的随从的位置,求最多最少分别能消灭对方多少随从.
题解
完美团情况:普通破圣盾,剧毒撞普通
辣鸡团情况:剧毒撞圣盾,普通撞普通(是我本人下棋情况了)
然后贪心即可
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int T,n,a,b,c,d;
char S[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Work(){
register int i=0,x=0,A=a,B=b,C=c,D=d,Ans=0;
for (i=0;i<n;i++){
x=S[i]-48;
if (!x){
if (D) {D--,C++; continue;}
if (C) continue;
if (B) B--,A++;
continue;
}
if (C) {C--,Ans++; continue;}
if (D) {D--,C++; continue;}
if (A) {A--,Ans++; continue;}
if (B) B--,A++;
}
printf("%d ",Ans);
Ans=0; A=a; B=b; C=c; D=d;
for (i=0;i<n;i++){
x=S[i]-48;
if (!x){
if (C) continue;
if (D) {C++,D--; continue;}
if (A) continue;
if (B) {B--,A++; continue;}
continue;
}
if (D) {D--,C++; continue;}
if (C) {Ans++,C--; continue;}
if (B) {B--,A++; continue;}
if (A) {A--,Ans++; continue;}
}
printf("%d\n",Ans);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
scanf("%s",&S);
Work();
}
return 0;
}
[F] 图与三角形
题意
给出一个完全图,每条边为黑白两种颜色之一,求能构成多少种同色三角形
题解
不合法的三角形一定有一个点连出的两条边颜色不同.
对于每个点,统计出连出了多少白边,多少黑边,然后把不合法的方案数减去即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include <queue>
using namespace std;
long long int n, A, B, C, P, D;
long long int ans = 0, low = 0;
int map[10005][10005];
int main(){
cin >> n;
cin >> A >> B >> C >> P >> D;
for (int i = 1; i < n; i++)
for (int j = i+1; j <= n; j++)
if ((A*(i+j)*(i+j)+B*(i-j)*(i-j)+C) % P > D) map[i][j] = map[j][i] = 1;
else map[i][j] = map[j][i] = 0;
ans = n * (n-1) * (n-2) / 6;
for (int i = 1; i <= n; i++) {
long long int num1 = 0, num0 = 0;
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (map[i][j] == 1) num1++;
if (map[i][j] == 0) num0++;
}
low += num1 * num0;
}
ans -= low / 2;
cout << ans << endl;
return 0;
}
[G] 单调栈
题意
有一个1-n的排列,第i位记为a_{i}.定义f(i)为[1,i-1]中a_{i}的前驱对应的f值加1.
现在给出了一个残缺的f序列,要求写出字典序最小的a序列.
题解
贪心.
整个序列开头的f肯定是1,然后统计一下一共有多少个1,假设有k个,则把k,k-1,...,1填充到这些位置上.把第一位去掉,把所有位置的f值减去1,便得到了一个新的序列.重复以上过程不断填充.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 110
#define INF 0x3f3f3f3f
using namespace std;
int T,i,j,s,n;
int a[N],f[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Work(int x,int p){
register int i=0,t=0,s=0;
if (x>n) return;
if (a[x]) {Work(x+1,p); return;}
f[x]=1;
for (i=x;i<=n;i++) s+=(f[i]==1);
t=p+s;
for (i=x;i<=n;i++)
if (f[i]==1) a[i]=p+(--s);
for (i=x;i<=n;i++) f[i]--;
Work(x+1,t);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read(); memset(f,0,sizeof(f));
for (i=1;i<=n;i++) f[i]=read();
memset(a,0,sizeof(a));
Work(1,1);
for (i=1;i<n;i++) printf("%d ",a[i]);
printf("%d\n",a[n]);
}
return 0;
}
[I] 变大!
题意
给出一个序列a,每一次可以对某个位置执行一次操作,假设选择了第i位,则a_{i}=a_{i-1}=a_{i+1}=Max(a_{i},a_{i+1},a_{i+2})
现在进行了k(1\leq k \leq n)次操作,求序列之和的最大值是多少.对于所有的k,都要求出答案.
题解
假设有一段长度为l的序列,根据上面的操作的定义,不难证明,只需要\frac{l}{2}次就可以把这个序列的每一位都变成原序列中的最大值.
定义f[i][j]表示前i位执行了j次操作所能够达到的最大值.执行了一定次数的操作后,序列会变成很多"小块",每一块的值相同.于是可以根据背包的思想进行转移.转移方程为
f[i][k+l]=Max(f[i][k+l],f[j][k]+Max(a_{j+1}^{i})*(i-j))
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int T,i,j,k,n,l,Ans,s;
int a[N],f[N][N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read();
for (i=1;i<=n;i++) a[i]=read();
memset(f,0,sizeof(f));
for (i=1;i<=n;i++){
s=a[i];
for (j=i-1;j>=0;j--){
l=(i-j)/2;
for (k=0;k+l<=n;k++)
f[i][k+l]=Max(f[i][k+l],f[j][k]+(i-j)*s);
s=Max(s,a[j]);
}
}
for (i=1;i<n;i++) printf("%d ",f[n][i]);
printf("%d\n",f[n][n]);
}
return 0;
}
[K] 最大权值排列
题意
对于一个长度为n的序列A,定义其权值f(A)为
f(A)=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\sum_{k=i}^{j}A_{k}}{j-i+1}
现在给出了n,要求给出一个1-n的排列P,使得f(P)尽可能地大.给出字典序最小的那个.
题解
找规律后不难发现,把较大的数尽量往中间放就行了.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int main(){
int n;
cin >> n;
for (int i = 1; i <= n; i += 2) printf("%d ", i);
if (n % 2) for (int i = n - 1; i >= 2; i -= 2) printf("%d ", i);
else for (int i = n; i >= 2; i -= 2) printf("%d ", i);
return 0;
}
[L] 你吓到我的马了.jpg
题意
给出一个棋盘,棋盘上有一些障碍.棋盘上还有一个中国象棋中的马(也就是说可以被蹩马腿).现在要求求出这个马跳到棋盘上每一个地方分别最少需要几步.障碍不能通过.
题解
BFS
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include <queue>
using namespace std;
int n, m, ans[105][105], map[105][105], stx, sty;
char s[105];
queue <int> l;
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%s", s);
for (int j = 0; j < m; j++) {
if (s[j] == 'M') { map[i][j+1] = 0; stx = i; sty = j+1; }
if (s[j] == 'X') { map[i][j+1] = -1; }
if (s[j] == '.') { map[i][j+1] = 1; }
}
}
for (int i = 1; i <= n; i++) map[i][0] = map[i][m+1] = -1;
for (int i = 1; i <= m; i++) map[0][i] = map[n+1][i] = -1;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) ans[i][j] = 99999;
ans[stx][sty] = 0;
l.push(stx * 1000 + sty);
while(!l.empty()) {
int a = l.front();
int x = a/1000, y = a%1000;
//printf("%d %d\n", x, y);
//int k; scanf("%d", &k);
l.pop();
if (x > 2) if (map[x-1][y] != -1) {
if (y > 1) if (map[x-2][y-1] == 1 && ans[x-2][y-1] > ans[x][y] + 1) {
ans[x-2][y-1] = ans[x][y] + 1;
int aimx = x - 2, aimy = y - 1;
l.push(aimx * 1000 + aimy);
}
if (y < m) if (map[x-2][y+1] == 1 && ans[x-2][y+1] > ans[x][y] + 1) {
ans[x-2][y+1] = ans[x][y] + 1;
int aimx = x - 2, aimy = y + 1;
l.push(aimx * 1000 + aimy);
}
}
if (x > 1) {
if (y > 2) if (map[x][y-1] != -1) if (map[x-1][y-2] == 1 && ans[x-1][y-2] > ans[x][y] + 1) {
ans[x-1][y-2] = ans[x][y] + 1;
int aimx = x - 1, aimy = y - 2;
l.push(aimx * 1000 + aimy);
}
if (y < m-1) if (map[x][y+1] != -1) if (map[x-1][y+2] == 1 && ans[x-1][y+2] > ans[x][y] + 1) {
ans[x-1][y+2] = ans[x][y] + 1;
int aimx = x - 1, aimy = y + 2;
l.push(aimx * 1000 + aimy);
}
}
if (x < n) {
if (y > 2) if (map[x][y-1] != -1) if (map[x+1][y-2] == 1 && ans[x+1][y-2] > ans[x][y] + 1) {
ans[x+1][y-2] = ans[x][y] + 1;
int aimx = x + 1, aimy = y - 2;
l.push(aimx * 1000 + aimy);
}
if (y < m-1) if (map[x][y+1] != -1) if (map[x+1][y+2] == 1 && ans[x+1][y+2] > ans[x][y] + 1) {
ans[x+1][y+2] = ans[x][y] + 1;
int aimx = x + 1, aimy = y + 2;
l.push(aimx * 1000 + aimy);
}
}
if (x < n - 1) if (map[x+1][y] != -1) {
if (y > 1) if (map[x+2][y-1] == 1 && ans[x+2][y-1] > ans[x][y] + 1) {
ans[x+2][y-1] = ans[x][y] + 1;
int aimx = x + 2, aimy = y - 1;
l.push(aimx * 1000 + aimy);
}
if (y < m) if (map[x+2][y+1] == 1 && ans[x+2][y+1] > ans[x][y] + 1) {
ans[x+2][y+1] = ans[x][y] + 1;
int aimx = x + 2, aimy = y + 1;
l.push(aimx * 1000 + aimy);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (ans[i][j] != 99999) printf("%d ", ans[i][j]);
else printf("-1 ");
cout << endl;
}
return 0;
}
[M] 自闭
题意
一些人在刷一些题,不同的通过情况会产生不同的自闭点数,求最后每个人的自闭点数.
题解
模拟
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 110
#define INF 0x3f3f3f3f
using namespace std;
int i,j,n,m,w;
int Ans[N],f[N][N],v[N],ed[N],t[N],s[N],k[N];
vector <int> Q[N][N];
struct Data{
int x,y,r;
}a[N];
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Ready(){
register int i=0,j=0,sum=0;
for (i=1;i<=w;i++){
if (a[i].r==1) f[a[i].x][a[i].y]=1;
v[a[i].x]=1;
}
for (i=1;i<=n;i++)
if (!v[i]) Ans[i]=998244353,ed[i]=1;
// 1
for (i=1;i<=n;i++){
if (ed[i]) continue;
for (j=1;j<=m;j++)
if (f[i][j]) goto END;
Ans[i]=1000000; ed[i]=1;
END:;
} // 2
for (i=1;i<=n;i++){
sum=0;
if (ed[i]) continue;
for (j=1;j<=m;j++) sum+=f[i][j];
if (sum==m) Ans[i]=0,ed[i]=1;
} // 3
}
inline void Work(){
register int i=0,j=0,x=0,y=0;
for (i=1;i<=w;i++)
if (a[i].r) t[a[i].y]=1;
for (j=1;j<=m;j++)
for (i=1;i<=n;i++)
s[j]+=f[i][j];
for (j=1;j<=m;j++){
if (!t[j]) continue;
for (i=1;i<=n;i++){
if (ed[i]) continue;
if (!f[i][j]) Ans[i]+=20;
if (!f[i][j] && s[j]>=(n/2)) Ans[i]+=10;
}
} // 4&5
for (i=1;i<=w;i++){
if (ed[a[i].x]) continue;
Q[a[i].x][a[i].y].push_back(a[i].r);
}
for (i=1;i<=n;i++){
if (ed[i]) continue;
memset(k,0,sizeof(k));
for (j=1;j<=m;j++){
x=0;
for (auto p : Q[i][j]){
if (p) {
k[j]=Max(k[j],x); x=0;
} else x++;
}
k[j]=Max(k[j],x);
}
for (j=1;j<=m;j++){
Ans[i]+=k[j]*k[j];
if (!f[i][j]) Ans[i]+=k[j]*k[j];
}
} // 6&7
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read(); w=read();
for (i=1;i<=w;i++){
a[i].x=read(); a[i].y=read(); a[i].r=read();
}
Ready(); Work();
for (i=1;i<=n;i++) printf("%d\n",Ans[i]);
return 0;
}
[N] 合并!
题意
有一行长度为n石子堆,第i堆有一个重量a_{i}.每一次可以把相邻两堆石子合并,并得到a_{i}a_{i+1}的分数,新的石子堆的重量为a_{i}+a_{i+1}.求最后合并成一堆后,能拿到的最大分数是多少.
题解
推导后不难发现,答案是每一堆石子重量两两之积的总和.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int s[2005], n;
long long int ans = 0;
int main(){
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
for (int j = 1; j < i; j++) ans += s[i] * s[j];
}
cout << ans << endl;
return 0;
}
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020 CCPC Winter Camp Day6 题解
本文地址: 2020 CCPC Winter Camp Day6 题解
