写在前面
全文收集了部分学长以及我自己的代码，本蒟蒻第一次写博客，效果不好请见谅TwT
原题链接：https://ac.nowcoder.com/acm/contest/46800#question
A：World Final? World Cup! (I)
模拟，没啥讲的啦
B：World Final? World Cup! (II)
题目大意：n<=40场球赛，甲队总共进球数为x，乙队总共进球数为y，x,y<=120，对于每场球赛胜者加3分，败者不加分，平局两队各加1分。求这n轮有多少种不同的比赛结果使得本赛季某队获得至少m<=120分。之中对于两种比赛结果，若nn轮比赛中至少有一场的比分不一样，就认为两种比赛结果不同。
- Scarlett的小屁孩的数学写法
组合数学，不会的补习去https://oi-wiki.org/math/combinatorics/combination/ 看前面一部分就行了，后面的我也不会。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
ll fac[1000],inv[1000];
ll powmod(ll a,ll b) {
ll re=1;
while(b) {
if(b&1) re=re*a%mod;
b>>=1;
a=a*a%mod;
}
return re;
}
ll C(int n,int m) {
if(n<0) return 0;
if(m<0) return 0;
if(m>n) return 0;
return p[n]*inv[n-m]%mod*inv[m]%mod;
}
int main() {
fac[0]=1;
for(int i=1; i<=200; i++) {//求阶乘
fac[i]=fac[i-1]*i%mod;
}
inv[200]=powmod(inv[200],mod-2);
for(int i=199; i>=0; i--) {//因为组合数涉及除法，求一下各阶乘的逆元
inv[i]=inv[i+1]*(i+1)%mod;
}
int n,m,x,y;
scanf("%d%d%d%d",&n,&m,&x,&y);
ll ans=0;
for(int a=0; a<=x; a++) {//枚举甲队的净赢球数
int b=y+a-x;//已队的净赢球数
if(b<0) continue;
for(int i=0; i<=n; i++) { //i 表示赢几场
for(int j=n-i; j>=0; j--) { // j 表示输几场
int k=n-i-j;// k 表示平几场
if(i*3+k<m) continue;
if(i==0&&a>0) continue;
if(j==0&&b>0) continue;
if(a==0&&i>0) continue;
if(b==0&&j>0) continue;
if(i>a||j>b) continue;
ll re=C(n,i)*C(n-i,j)%mod*C(n+x-a-1,n-1)%mod;
if((j==0&&b==0)&&(i==0&&a==0)) re=re%mod ;
else if(j==0&&b==0) re=re*C(a-1,i-1)%mod;
else if(i==0&&a==0) re=re*C(b-1,j-1)%mod;
else re=re*C(a-1,i-1)%mod*C(b-1,j-1)%mod;
ans=(ans+re)%mod;
}
}
}
printf("%lld\n",ans);
return 0;
}
- 牛哇哇哇哇的dp写法
我还没完全看懂，先贴出来，待我吃透了再更新
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int dp[2][130][105][105];
int tag[4][2][125][105][105];
void add(int &a,int b) {
a+=b;
if(a>=mod)a-=mod;
}
void del(int &a,int b) {
a-=b;
if(a<=0)a+=mod;
}
int mul(int a,int b) {
return 1ll*a*b%mod;
}
int calc(int id,int now,int x,int y,int z) {
if(x<0||y<0||z<0|z>100)return 0;
return tag[id][now][x][y][z];
}
int main() {
int n,m,x,y;
scanf("%d%d%d%d",&n,&m,&x,&y);
for(int _t=0; _t<=n; _t++) {
int now=(_t&1),nxt=1-now;
memset(dp[now],0,sizeof(dp[now]));
memset(tag[1][nxt],0,sizeof(tag[1][nxt]));
memset(tag[2][nxt],0,sizeof(tag[2][nxt]));
memset(tag[3][nxt],0,sizeof(tag[3][nxt]));
if(_t==0)dp[now][0][0][0]=1;
for(int i=0; i<=(_t+1)*3; i++) {
for(int j=0; j<=x; j++) {
for(int k=0; k<=y; k++) {
add(dp[now][i][j][k],calc(1,now,i,j,k-1));
add(dp[now][i][j][k],calc(2,now,i-3,j-1,k));
add(dp[now][i][j][k],calc(3,now,i-1,j,k));
}
}
for(int j=0; j<=x; j++) {
for(int k=0; k<=y; k++) {
add(tag[3][nxt][i][j][k],dp[now][i][j][k]);
add(tag[3][nxt][i][j][k],calc(3,nxt,i,j-1,k-1));
add(tag[1][nxt][i][j][k],dp[now][i][j][k]);
add(tag[1][nxt][i][j][k],calc(1,nxt,i,j,k-1));
add(tag[1][nxt][i][j][k],calc(1,nxt,i,j-1,k-1));
del(tag[1][nxt][i][j][k],calc(1,nxt,i,j-1,k-2));
add(tag[2][nxt][i][j][k],dp[now][i][j][k]);
add(tag[2][nxt][i][j][k],calc(2,nxt,i,j-1,k));
add(tag[2][nxt][i][j][k],calc(2,nxt,i,j-1,k-1));
del(tag[2][nxt][i][j][k],calc(2,nxt,i,j-2,k-1));
}
}
}
}
int ans=0;
for(int i=m; i<=120; i++) {
int now=(n&1);
add(ans,dp[now][i][x][y]);
}
printf("%d",ans);
return 0;
}
C: 现在是，学术时间 (I)
懒得写
D: 现在是，学术时间 (II)
题目大意：给出一个由平面上两点(0,0),(x,y)所确定的一个矩形A和一个点P(xp,yp)。请你求出在所有以P点作为其中一个顶点且边都平行于坐标轴的矩形B中，交集面积/并集面积的值最大为多少。
分类讨论点P相对于(x,y)的位置，写出值的表达式并分析未给出点在矩形A的哪个顶点时值最大。
注意取绝对值用fabs()
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
double x,y,xp,yp;
double s,sp;
int main(){
int T;
cin>>T;
while(T--){
cin>>x>>y>>xp>>yp;
double s0=x*y,s1=xp*yp,s2=xp*fabs(y-yp),s3=yp*fabs(x-xp),s4=fabs(x-xp)*fabs(y-yp);
if(xp<=x){
if(yp<=y){
double ans=max(s1,s2);
ans=max(ans,max(s3,s4));
ans=ans/s0;
printf("%.9lf\n",ans);
}else{
double a=max(xp,x-xp),b=yp-y;
double ans=a*y/(s0+a*b);
printf("%.9lf\n",ans);
}
}else{
if(yp<=y){
double a=max(yp,y-yp),b=xp-x;
double ans=a*x/(s0+a*b);
printf("%.9lf\n",ans);
}else{
double ans=s0/s1;
printf("%.9lf\n",ans);
}
}
}
}
E: 鸡算几何
题目大意：平面上有一个L型铁丝ABC，规定中间字母为L的拐角。给出原先ABC以及变化后DEF各点坐标，问ABC能否只通过平面上的平移旋转得到DEF？
可以先在纸上写个L自己模拟转一下，可以发现如果以长边竖直，拐角在下的视角看去，短边永远在左侧或永远在右侧。
于是可以通过鞋带定理，以长边端点-拐角-短边端点的顺序求值，如果顺序为顺时针值为负，逆时针为正。
而两边等长分不出长短边，也无法判断是否进行过三维变换。
注意：浮点比较不能用==，判断差值的绝对值是否小于误差就行了
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
struct node{
double x,y;
}poi[10];
inline double dis(int i,int j){
node x=poi[i],y=poi[j];
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double Exp=0.000000001;
int main(){
int T;
cin>>T;
while(T--){
for(int i=1;i<=6;i++){
cin>>poi[i].x>>poi[i].y;
}
double lenmx=dis(1,2),lenmn=dis(2,3);
int mx=1;
if(lenmx<lenmn) swap(poi[1],poi[3]);
if(fabs(lenmx-lenmn)<Exp){
cout<<"NO\n";
continue;
}
double slenmx=dis(4,5),slenmn=dis(5,6);
int smx=4;
if(slenmx<slenmn) swap(poi[4],poi[6]);
double ans1=0,ans2=0;
for(int i=1;i<=3;i++) ans1+=poi[i].x*(poi[(i==3?1:i+1)].y-poi[(i==1?3:i-1)].y);
for(int i=4;i<=6;i++) ans2+=poi[i].x*(poi[(i==6?4:i+1)].y-poi[(i==4?6:i-1)].y);
if((ans1<0&&ans2<0)||(ans1>0&&ans2>0)) cout<<"NO\n";
else cout<<"YES\n";
}
}
F: 鸡玩炸蛋人
题目大意就懒写了，反正看的都是集训队的
简单并查集
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
ll a[100100],fa[100100],sum[100100];
inline int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
inline void merge(int x,int y){//sum记录每个集的节点数
x=find(x),y=find(y);
if(x==y) return;
fa[x]=y;
sum[y]+=sum[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
sum[i]=1;
}
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
merge(u,v);
}
int fl=1,k=0;//明显只有炸弹都在同一集内才有可能放置
//fl为1表示所有节点都没放
//2表示炸弹在不同集
//0表示炸弹在同一集
//k纪律炸弹在以谁为祖先的集内
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]){
if(fl==1) fl=0;
int g=find(i);
if(k==0) k=g;
if(k!=g) fl=2;
}
}
//可以发现在一个集内，每个节点都可以成为S或T，故方案数为集节点数的平方
//我不太会描述，可以手动模拟一下，类似于图的遍历，你可以回溯的时候再放炸弹，所以不用担心炸弹挡路
if(fl==2) cout<<0;
else if(fl==1){
ll ans=0;
for(int i=1;i<=n;i++) if(fa[i]==i){
ans+=sum[i]*sum[i];
}
cout<<ans;
}else{
cout<<sum[k]*sum[k];
}
}
G: 鸡格线
1.线段树维护，暴力修改
这题写过基本一样的啊，可惜我最后5分钟才看题没时间写了
先手动模拟一下函数f(x)，带入最大值1e9，发现11次后得到100，所以对于每个区间记录次数，超过11次就之间返回，我因为怕翻车就设定为13次了。
对于询问直接输出节点1的值。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls i<<1
#define rs i<<1|1
#define mid (l+r>>1)
#define endl '\n'
#define N 100100
int n,m;
ll val[N<<2],lz[N<<2];
inline void pu(int i){
val[i]=val[ls]+val[rs];
}
inline void build(int i,int l,int r){
val[i]=lz[i]=0;
if(l==r){
scanf("%lld",&val[i]);
return ;
}
build(ls,l,mid),build(rs,mid+1,r);
pu(i);
}
inline void upd(int i,int l,int r,int x,int y,int k){
if(x<=l&&r<=y){
if(lz[i]>=13) return;
else lz[i]+=k;
}
if(l==r){
for(int j=1;j<=k;j++){
val[i]=(int)(10.0*sqrt(val[i])+0.5);
}
return ;
}
if(x<=mid) upd(ls,l,mid,x,y,k);
if(mid<y) upd(rs,mid+1,r,x,y,k);
pu(i);
}
int main(){
scanf("%d%d",&n,&m);
build(1,1,n);
int op,x,y,k;
while(m--){
scanf("%d",&op);
if(op==1){
scanf("%d%d%d",&x,&y,&k);
k=min(13,k);
if(k)upd(1,1,n,x,y,k);
}else{
printf("%lld\n",val[1]);
}
}
}
2.STL
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int T = 1;
while(T--){
int n,m;
cin>>n>>m;
LL sum = 0;
map<int,int> a;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[i] = x;
sum += x;
}
a[n+1] = 1;
a[-1] = 1;
while(m--){
int t;
cin>>t;
if(t==2) cout<<sum<<endl;
else{
int l,r,k;
cin>>l>>r>>k;
for(auto it=a.lower_bound(l);it->first<=r;it++){
auto &[i,y] = *it;
for(int j=1;j<=k;j++){
int x = round(sqrt(y)*10);
sum -= y;
sum += x;
if(x==y){
it = a.erase(it);
it--;
break;
}
y = x;
}
}
}
}
}
return 0;
}
H: 本题主要考察了DFS
我信了他的鬼话，dfs写了半天。。。
“这H 我愿称其为质量守恒”
#include<bits/stdc++.h>
using namespace std;
int n,T,cnt;
int main(){
cin>>T;
while(T--){
cin>>n;
cnt=n*n-1;
int p=10;
for(int i=1;i<=cnt;i++){
string s;
cin>>s;
for(int j=0;j<4;j++){
if(s[j]=='1') p++;
else if(s[j]=='2') p--;
}
}
cout<<p<<endl;
}
}
I: 本题也主要考察了DFS
注意：牛牛点最多只要一个！！！
Scarlett的小屁孩的代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;
const int N = 1e5 + 10;
int a[110][110];
bool vis[110][110];//是否为牛牛点
bool used[10010];//当前数字是否被用过
int n, m, t;
void No() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("0%c", j == n ? '\n' : ' ');
}
}
}
void Print() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%d%c", a[i][j], j == n ? '\n' : ' ');
}
}
}
bool check(int x, int y) {
int Max = 0, Min = 1e9;
for (int i = 1; i <= n; i++) {
Max = max(Max, a[x][i]);
Min = min(Min, a[i][y]);
}
if (Max != a[x][y] || Min != a[x][y])return 0;
return 1;
}
void solve() {
memset(used, 0, sizeof used);
memset(a, 0, sizeof a);
memset(vis, 0, sizeof vis);
scanf("%d%d",&n,&m);
for (int i = 1,op,x,y,k; i <= m; i++) {
scanf("%d%d%d",&op,&x,&y);
if (op == 1) {
scanf("%d",&k);
a[x][y] = k;
used[k] = 1;
} else {
vis[x][y] = 1;
}
}
int cnt = 0;//统计牛牛点数量
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cnt += vis[i][j];
}
}
if (cnt > 1) {//大于一个打印0矩阵
No();
return;
}else if (cnt == 0) {//没有牛牛点
int P = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j]) continue;
while (used[P]) P++;//如果这个数字被用过之间跳过
used[P] = 1;
a[i][j] = P;
}
}
Print();
} else if (cnt == 1) {
int L = 1, R = n * n;//上下界
int x, y;//记录牛牛点的坐标
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (vis[i][j]) {
x = i, y = j;
break;
}
}
}
for (int i = 1; i <= n; i++) {//遍历牛牛点所在列
if (i == x) continue;//先跳过牛牛点，因为它只能是列中最小的
if (a[i][y]) continue;//赋过值就跳过
while (used[R]) R--;//尽量放大的
if (R <= 0) {//如果没数可放说明失败了
No();
return;
}
used[R] = 1;
a[i][y] = R;
}
for (int i = 1; i <= n; i++) {
//因为牛点只能是列内最小的，但之前因为要尽量放大数所以直接跳过了已赋值点
//现在出了牛点都要遍历，更新R为列内除牛点外最小值-1，即牛点值的上界
if (i == x) continue;
R = min(R, a[i][y] - 1);
}
while (used[R])R--;//但是R可能被用过了，还需要更新一次，现在R是真正的牛点值的上界
for (int i = 1; i <= n; i++) {//现在遍历牛点所在行，原理同上
if (i == y) continue;
if (a[x][i]) continue;
while (used[L]) L++;
if (L > n * n) {
No();
return;
}
used[L] = 1;
a[x][i] = L;
}
for (int i = 1; i <= n; i++) {
if (i == y) continue;
L = max(L, a[x][i] + 1);
}
while (used[L])L++;
if (!a[x][y] && L <= R) {//如果牛点没赋值且上下界内可以取值
a[x][y] = L;
used[L] = 1;
} else if (!a[x][y]) {//如果牛点没赋值且上下界内不可以取值
No();
return;
}
int P = 1;
for (int i = 1; i <= n; i++) {//填数
for (int j = 1; j <= n; j++) {
if (a[i][j]) continue;
while (used[P]) P++;
used[P] = 1;
a[i][j] = P;
}
}
//注意！之前遍历牛点所在行列时遇到已赋值的点是直接跳过去的
//现在要检查赋的值是否合理了
if (check(x, y)) Print();
else No();
}
}
int main() {
scanf("%d",&t);
while (t--)
solve();
return 0;
}
J: 本题竟也主要考察了DFS
Scarlett的小屁孩的代码
极其恼人的分类讨论，我逻辑还没彻底理清，先留一坑
#include<bits/stdc++.h>
using namespace std;
int a,b,c,t;
void solve() {
scanf("%d%d%d",&a,&b,&c);
if (a == 0) {
printf("1\n");
return;
}
if ((a & c) != c) {
printf("1\n");
return;
}
if (b == 0) {
printf("2\n");
return;
}
if (b != c && c != 0) {
printf("2\n");
return;
}
if (b == c) {
printf("2\n");
return;
}
printf("-1\n");
}
int main() {
cin>>t;
while (t--)
solve();
return 0;
}
K: 本题主要考察了dp
可以发现1001001001...可以在使用0数量最少的情况下让坏串最少
#include<bits/stdc++.h>
using namespace std;
int n,m,c;
int a[1100];
int cnt=0;
int main() {
cin>>n>>m;
c=n-m;//0的数量
for(int i=1,j=0; i<=n; i++,j--) {
if(j==0) {//当j为0时说明现在可以放1了
if(m) {//如果1有剩余
m--;
a[i]=1;
j=3;
} else {//如果1用完了
c--;
a[i]=0;
}
} else {//现在不适合放1
if(c){//如果0有剩余
c--;
a[i]=0;
}else{//0用完了只能放1了
m--;
a[i]=1;
}
}
}
for(int i=1;i<=n-2;i++){//放完后直接统计坏串数
int cnt0=0,cnt1=0;
for(int j=i;j<=i+2;j++){
if(a[j]) cnt1++;
else cnt0++;
}
if(cnt1>cnt0) cnt++;
}
cout<<cnt;
}
L: 本题主要考察了运气
高中概率
M: 本题主要考察了找规律
牛哇哇哇哇的代码
“看到题目不考虑dp就不算入门”
#include<bits/stdc++.h>
using namespace std;
int n,m;
double dp[550][550];//1~i个朋友分完了j个先辈的好感动和
int main(){
cin>>n>>m;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=-1e18;//不要用memset赋值，否则结果很奇怪
}
}
dp[0][0]=0;
for(int i=0;i<n;i++){//枚举朋友，因为转移给i+1，所以[0,n-1]
for(int j=0;j<=m;j++){
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);//如果不给第i+1个朋友先辈
for(int k=1;k<=m-j;k++){//枚举要给i+1个朋友多少个
dp[i+1][j+k]=max(dp[i+1][j+k],dp[i][j]+1.0*k/(m-j));
}
}
}
double ans=dp[n][m];
printf("%.9lf",ans);
}
总结
严重的标题欺骗！不应该死磕某道题或者某种算法。
标签：return,re,int,题解,ll,long,牛客,集训营,mod From： https://www.cnblogs.com/EndPB/p/17058166.html