Wannafly Winter Camp 2020-Day6

手速场 今天是废物

开局挑了个题目 “自闭” 一看 哦 小模拟 这个我学得来
和队友说 有个模拟 我去写了 同时立下flag:前三小时可能没我了
写完后因为傻逼和语文太差被关了半小时
这时候已经写得差不多了 没我啥事了
去想J 然后被关到比赛结束 玄学做法果然不可取
赛后dp补了

6C. 酒馆战棋

最不爱写的题 队友代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
char s[1005];
int main(){
int _; sc(_); while(_--){
int n,a,b,c,d; sc(n),sc(a),sc(b),sc(c),sc(d),scs(s);
int aa=a,bb=b,cc=c,dd=d,mx=0,mn=0; rep(i,0,n){
if(s[i]=='0'){
if(dd) dd--,cc++; else if(cc){ } else if(bb) bb--,aa++;
}
else{
if(cc) mx++,cc--; else if(dd) dd--,cc++;
else if(aa) aa--,mx++; else if(bb) bb--,aa++;
}
}
aa=a,bb=b,cc=c,dd=d; rep(i,0,n){
if(s[i]=='0'){
if(cc){ } else if(dd) dd--,cc++;
else if(aa){ } else if(bb) bb--,aa++;
}
else{
if(dd) dd--,cc++; else if(cc) cc--,mn++;
else if(bb) bb--,aa++; else if(aa) aa--,mn++;
}
} pf("%d %d\n",mx,mn);
}
}

6F. 图与三角形

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
ll n,a,b,c,p,d,ans;
vector<int>vv[5005];
int main(){
scl(n); scl(a); scl(b); scl(c); scl(p); scl(d);
rep(i,1,n+1) rep(j,1,n+1) if(i!=j&&(a*(i+j)*(i+j)+b*(i-j)*(i-j)+c)%p>d) vv[i].push_back(j);
rep(i,1,n+1) ans+=vv[i].size()*(n-vv[i].size()-1);
ans=n*(n-1)*(n-2)/6-ans/2; printf("%lld\n",ans);
}

6K. 最大权值排列

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
int main(){
int n,cnt(1); sc(n); rep(i,1,n+1){
if(i&1) a[cnt]=i; else a[n-cnt+1]=i,cnt++;
} rep(i,1,n+1) pf("%d ",a[i]);
}

6L. 你吓到我的马了.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
char mp[105][105];
int n,m,vis[105][105],ans[105][105];
int dir[8][2]={2,1,2,-1,-2,1,-2,-1,1,2,1,-2,-1,2,-1,-2};
struct node{ int x,y,cnt; }s;
void bfs(){
ans[s.x][s.y]=0; vis[s.x][s.y]=1;
queue<node>q; q.push(s); while(!q.empty()){
node fr=q.front(); q.pop();
ans[fr.x][fr.y]=fr.cnt; rep(i,0,8){
node t=fr; t.x+=dir[i][0],t.y+=dir[i][1],t.cnt++;
if(t.x<0||t.y<0||t.x>=n||t.y>=m) continue;
if(vis[t.x][t.y]||mp[t.x][t.y]=='X') continue;
if(mp[fr.x+dir[i][0]/2][fr.y+dir[i][1]/2]=='X') continue;
q.push(t); vis[t.x][t.y]++;
}
}
}
int main(){
sc(n); sc(m); rep(i,0,n){
scs(mp[i]); rep(j,0,m) if(mp[i][j]=='M') s.x=i,s.y=j,s.cnt=0;
} mst(ans,-1); bfs();
rep(i,0,n) rep(j,0,m) pf("%d%c",ans[i][j],j==m-1?'\n':' ');
}

6M. 自闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int q[105][15][2]; //计数
int vis[105],ac[105]; //vis这个人有没有交过 ac这个人有没有提交过
int sd[15]; //solved
int wa[105][15];
int main(){
int n,m,w; sc(n); sc(m); sc(w); rep(i,0,w){
int x,y,c; sc(x); sc(y); sc(c);
q[x][y][c]++; vis[x]++; if(c){ //如果是ac
if(q[x][y][0]) wa[x][y]=max(wa[x][y],q[x][y][0]),q[x][y][0]=0;
ac[x]++; if(q[x][y][1]==1) sd[y]++; //不重复计算ac人数
}
} rep(i,1,n+1) rep(j,1,m+1) if(q[i][j][0]) wa[i][j]=max(wa[i][j],q[i][j][0]);
rep(i,1,n+1){
if(!vis[i]) puts("998244353"); //没提交
else if(!ac[i]) puts("1000000"); //爆零
else{
int ak(1); rep(j,1,m+1) if(!q[i][j][1]) ak=0;
if(ak) puts("0"); else{
//4 有人a自己没a +20
//5 过半人a自己没a +10
int ans(0); rep(j,1,m+1) if(!q[i][j][1]&&sd[j]){
ans+=20; if(sd[j]>=n/2) ans+=10;
}
//6 连wa k次 +k^2
//7 连wa k次且没a +k^2
rep(j,1,m+1){
int k=wa[i][j]; k*=k; ans+=k;
if(!q[i][j][1]) ans+=k;
} pf("%d\n",ans);
}
}
}
}

6N. 合并!

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
int a[2005];
int main(){
int n; ll ans(0); sc(n); rep(i,0,n) sc(a[i]); sort(a,a+n);
if(n==1) return pf("%d\n",a[0]),0;
rep(i,0,n-1) ans+=1ll*a[i]*a[i+1],a[i+1]+=a[i];
pf("%lld\n",ans);
}

补题:

6G. 单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
int a[105],ans[105];
int main(){
int _; sc(_); while(_--){
int n; sc(n); rep(i,0,n) sc(a[i]);
int cnt(0),pos(0); mst(ans,0); rep(i,1,n+1){
while(pos<n&&ans[pos]) pos++;
if(pos==n) break; if(a[pos]==-1) a[pos]=i;
dep(j,n-1,pos) if(a[j]==i) ans[j]=++cnt;
} rep(i,0,n) pf("%d%c",ans[i],i==n-1?'\n':' ');
}
}

6J. K重排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int jc[55],inv[55];
int dp[55],tmp[55];
int q[55][55][55];
int qpow(int x,int y){
int ans=1; while(y){
if(y&1) ans=1ll*ans*x%mod; x=1ll*x*x%mod; y>>=1;
} return ans;
}
int C(int s,int x){
return 1ll*jc[x]*inv[s]%mod*inv[x-s]%mod;
}
void init(){
jc[0]=inv[0]=1; rep(i,1,51) jc[i]=1ll*jc[i-1]*i%mod,inv[i]=qpow(jc[i],mod-2);
rep(i,1,51) rep(j,i,51) rep(k,1,j/i+1) if(k==1) q[i][j][k]=C(i,j);
else q[i][j][k]=1ll*q[i][j-i][k-1]*C(i,j)%mod;
}
void solve(){
int n; ll k; sc(n); scl(k); mst(dp,0); dp[0]=1; rep(i,1,n+1){
if(k%i) continue; memcpy(tmp,dp,sizeof(dp));
rep(j,0,n+1) for(int t=1,a=jc[i-1];j+t*i<=n;++t,a=1ll*a*jc[i-1]%mod)
dp[j+t*i]=(1ll*dp[j+t*i]+1ll*tmp[j]*q[i][n-j][t]%mod*a%mod*inv[t])%mod;
} pf("%d\n",dp[n]);
}
int main(){
init(); int _; sc(_); while(_--) solve();
}