10.12考试总结
T1 最近公共祖先
预估得分: 100
实际得分: 20
最大得分: 100
用时:1小时10分 ~1小时20分
一看题目就知道肯定是找规律题
20pts:
就是直接暴力求lca，很简单
100pts:
以下是打的表:
2
22
142
734
3390
14718
61694
253438
1029118
用excel生成一下函数图像可以看出，是一个指数函数？
卧槽，昨天刚刚看了这东西,爽,这种东东一般都是x^y的加减形式
开始硬凑
由前三项可以看出x应该与2有关系，否则不好凑出2来,所以x取2
2的幂次
2^0 1
2^1 2
2^2 4
2^3 8
2^4 16
2^5 32
2^6 64
2^7 128
#include<bits/stdc++.h>
#define int long long int
using namespace std;
const int mod=1e9+7;
int n;
int ksm(int a,int b) {
int res=1;
while(b) {
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
signed main() {
// freopen("commonants.in","r",stdin);
// freopen("commonants.out","w",stdout);
cin>>n;
if(n<=9) {
if(n==1) {
cout<<2;
return 0;
}
if(n==2) {
cout<<22;
return 0;
}
if(n==3) {
cout<<142;
return 0;
}
if(n==4) {
cout<<734;
return 0;
}
if(n==5) {
cout<<3390;
return 0;
}
if(n==6) {
cout<<14718;
return 0;
}
if(n==7) {
cout<<61694;
return 0;
}
if(n==8) {
cout<<253438;
return 0;
}
if(n==9) {
cout<<1029118;
return 0;
}
//n==10 忘记打表了
}
int ans=(ksm(2,2*n+2)-(((4*n)%mod+2)*(ksm(2,n)%mod))-2+mod)%mod;
while(ans<0)
{
ans+=mod;
}
ans=(ans+mod)%mod;
cout<<ans%mod;;
return 0;
}
错误原因
取模翻车，模出负数来了
应该是
(ans%mod+ans)%mod
T2 即时战略
预估得分：40
实际得分： 40
最大得分: 40
用时： 大约40分钟
10pts：
傻逼部分，差点忘了打上这部分的分，哦我真是傻逼
40pts
直接暴力统计，暴力计算
复杂度：O(n^4)
100pts
感觉上每个点的最大值，和最小值应该和他附近的点有关
感觉可以dp,如果有空再来搞
#include<bits/stdc++.h>
//#define int long long int
using namespace std;
const int N=444;
int w[N][N],n,h,p,ans;
int ans_max=0,ans_min=2147483647;
int d[N][N];//受损程度
#define fre
int main() {
#ifdef fre
freopen("rts.in","r",stdin);
freopen("r1.out","w",stdout);
#endif
cin>>n>>h>>p;
if(p==1) {
//10pts
for(int i=1; i<=n; ++i)
for(int j=1; j<=h; ++j) {
scanf("%d",&w[i][j]);
ans_max=max(w[i][j],ans_max);
ans_min=min(w[i][j],ans_min);
}
cout<<ans_min<<' '<<ans_max;
return 0;
}
//30pts
for(int i=1; i<=n; ++i)
for(int j=1; j<=h; ++j)
scanf("%d",&w[i][j]);
for(int i=1; i<=n; ++i) { //枚举投弹点的横坐标
for(int j=1; j<=h; ++j) { //枚举投弹点的纵坐标
ans=0;
for(int k=1; k<=n; ++k) {
for(int l=1; l<=h; ++l) {
d[k][l]=0;
int tmp=abs(i-k)+abs(j-l);
d[k][l]=max(0,p-tmp);
ans+=d[k][l]*w[k][l];
}
}
if(ans>ans_max) ans_max=ans;
if(ans<ans_min) ans_min=ans;
}
}
cout<<ans_min<<' '<<ans_max;
#ifndef fre
fclose(stdin);
fclose(stdout);
#endif
return 0;
}
T3 欧皇
预估得分：25
实际得分：25
最大得分: 40
用时：大约1小时多一点
10pts
w*h<=2 傻逼部分分，手玩就ok
可是我太菜了。不想手玩，于是就去搞搞其他部分分
25pts
w*h<=8
暴力枚举每个棋子放在那个格子里
卧槽翻车了.....看错时间
40pts
c1 一共就一颜色的棋子
可见就是要从ai个棋子里跳出一部分来放到wh的棋盘上，我们可以反过来搞
让wh的棋盘放ai个棋子有多少种方案，卧槽,这不是组合数嘛！！
C{nm,ai}i1
(⊙o⊙)…组合数怎么求来着.........一个悲惨的故事开始了....
55pts
ai==1 每种颜色的棋子都只有1个
卧槽这不是排列嘛！！！！
(⊙o⊙)…排列怎么求来着.........又一个悲惨的故事开始了....
等等好像不是，卧槽我不会这一档
100pts
卧槽我不会求排列和组合,部分分搞不到了，那就只能去搞搞正解了
没有特殊的限制.....应该去看看题目有什么特殊的性质或者是要求
两种方案不同当且仅当存在一个格子在两种方案中一种放
棋子一种不放棋子或放的棋子不一样
考虑20pts的做法
枚举每个棋子的情况 .仔细观察数据范围可以看出w,h的范围非常小<=30
所以可以直接当做状态来用
用dp[x][i][j]表示x这种棋子放在i,j格子是的合法情况
算了，不搞了，不会 ,不过sjp大佬肯定会!
#include<bits/stdc++.h>
#define int long long int
using namespace std;
const int mod=1e9+7;
const int N=2019;
int w,h,c;
int a[N],flag;
int C[N][N],visit[N][N];
int askC(int n,int k) {
if(visit[n][k]) return C[n][k];
if(k>n)return 0;
if(n==k||k==0) return 1;
visit[n][k]=1;
return C[n][k]=(askC(n-1,k-1)+askC(n-1,k))%mod;
}
int pts2() {
return askC(w*h,a[1]);
}
signed main() {
freopen("europe.in","r",stdin);
freopen("europe.out","w",stdout);
cin>>w>>h>>c;
for(int i=1; i<=c; ++i) {
cin>>a[i];
if(a[i]!=1) flag=1;
}
if(c==1) {//第2档分
cout<<pts2()%mod;
return 0;
}
if(w*h<=2) {//第1档分
if(!a[1]||!a[2]) {
cout<<3<<endl;
return 0;
} else {
cout<<0<<endl;
return 0;
}
}
if(flag==0) { //第3档分~~~想错了咕咕咕。，不是排列
while(1) {
break;
}
cout<<rand()<<15+rand()<<15%mod;
return 0;
}
cout<<rand()<<15+rand()<<15%mod;
return 0;
}