[日志]12-24
我不是柳橙汁
2017-12-24 20:54:47
### 1.今天考了一个考试。
分数235/300分。
A[暴力]
题意：队伍两两之间互相比赛，赢3分，平1分，负0分 问有多少种可能
观察数据范围n<=5
所以最多进行5\*(5-1)/2=10场比赛
最多只有3^10种可能
直接暴力即可
```cpp
#include<cstdio>
int p3[10][10][10],p4[10][10][10][10],p5[20][20][20][20][20];
int n,a,b,c,d,e;
inline void dfs3(int k,int n,int a,int b,int c){
if (k==n){
p3[a][b][c]++;
return;
}
if (k==0){
dfs3(1,n,a+3,b,c);
dfs3(1,n,a+1,b+1,c);
dfs3(1,n,a,b+3,c);
}
if (k==1){
dfs3(2,n,a,b+3,c);
dfs3(2,n,a,b+1,c+1);
dfs3(2,n,a,b,c+3);
}
if (k==2){
dfs3(3,n,a,b,c+3);
dfs3(3,n,a+1,b,c+1);
dfs3(3,n,a+3,b,c);
}
}
inline void dfs4(int k,int n,int a,int b,int c,int d){
if (k==n){
p4[a][b][c][d]++;
return;
}
else if (k==0){
dfs4(k+1,n,a+3,b,c,d);
dfs4(k+1,n,a+1,b+1,c,d);
dfs4(k+1,n,a,b+3,c,d);
}
else if (k==1){
dfs4(k+1,n,a+3,b,c,d);
dfs4(k+1,n,a+1,b,c+1,d);
dfs4(k+1,n,a,b,c+3,d);
}
else if (k==2){
dfs4(k+1,n,a,b+3,c,d);
dfs4(k+1,n,a,b+1,c+1,d);
dfs4(k+1,n,a,b,c+3,d);
}
else if (k==3){
dfs4(k+1,n,a+3,b,c,d);
dfs4(k+1,n,a+1,b,c,d+1);
dfs4(k+1,n,a,b,c,d+3);
}
else if (k==4){
dfs4(k+1,n,a,b+3,c,d);
dfs4(k+1,n,a,b+1,c,d+1);
dfs4(k+1,n,a,b,c,d+3);
}
else if (k==5){
dfs4(k+1,n,a,b,c+3,d);
dfs4(k+1,n,a,b,c+1,d+1);
dfs4(k+1,n,a,b,c,d+3);
}
}
inline void dfs5(int k,int n,int a,int b,int c,int d,int e){
if (k==n){
p5[a][b][c][d][e]++;
//printf("%d %d %d %d %d\n",a,b,c,d,e);
return;
}
else if (k==0){
dfs5(k+1,n,a+3,b,c,d,e);
dfs5(k+1,n,a+1,b+1,c,d,e);
dfs5(k+1,n,a,b+3,c,d,e);
}
else if (k==1){
dfs5(k+1,n,a+3,b,c,d,e);
dfs5(k+1,n,a+1,b,c+1,d,e);
dfs5(k+1,n,a,b,c+3,d,e);
}
else if (k==2){
dfs5(k+1,n,a,b+3,c,d,e);
dfs5(k+1,n,a,b+1,c+1,d,e);
dfs5(k+1,n,a,b,c+3,d,e);
}
else if (k==3){
dfs5(k+1,n,a+3,b,c,d,e);
dfs5(k+1,n,a+1,b,c,d+1,e);
dfs5(k+1,n,a,b,c,d+3,e);
}
else if (k==4){
dfs5(k+1,n,a,b+3,c,d,e);
dfs5(k+1,n,a,b+1,c,d+1,e);
dfs5(k+1,n,a,b,c,d+3,e);
}
else if (k==5){
dfs5(k+1,n,a,b,c+3,d,e);
dfs5(k+1,n,a,b,c+1,d+1,e);
dfs5(k+1,n,a,b,c,d+3,e);
}
else if (k==6){
dfs5(k+1,n,a+3,b,c,d,e);
dfs5(k+1,n,a+1,b,c,d,e+1);
dfs5(k+1,n,a,b,c,d,e+3);
}
else if (k==7){
dfs5(k+1,n,a,b+3,c,d,e);
dfs5(k+1,n,a,b+1,c,d,e+1);
dfs5(k+1,n,a,b,c,d,e+3);
}
else if (k==8){
dfs5(k+1,n,a,b,c+3,d,e);
dfs5(k+1,n,a,b,c+1,d,e+1);
dfs5(k+1,n,a,b,c,d,e+3);
}
else if (k==9){
dfs5(k+1,n,a,b,c,d+3,e);
dfs5(k+1,n,a,b,c,d+1,e+1);
dfs5(k+1,n,a,b,c,d,e+3);
}
}
int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
scanf("%d",&n);
if (n==2){
scanf("%d%d",&a,&b);
if (a==3&&b==0||a==1&&b==1||a==0&&b==3) printf("1\n");
else printf("0\n");
return 0;
}
else{
if (n==3) dfs3(0,3,0,0,0);
if (n==4) dfs4(0,6,0,0,0,0);
if (n==5) dfs5(0,10,0,0,0,0,0);
scanf("%d%d%d",&a,&b,&c);
if (n>=4) scanf("%d",&d);
if (n==5) scanf("%d",&e);
if (n==3){
if (a>6||b>6||c>6) printf("0\n");
else printf("%d\n",p3[a][b][c]);
return 0;
}
else if (n==4){
if (a>9||b>9||c>9||d>9) printf("0\n");
else printf("%d\n",p4[a][b][c][d]);
return 0;
}
else{
if (a>12||b>12||c>12||d>12||e>12) printf("0\n");
else printf("%d\n",p5[a][b][c][d][e]);
return 0;
}
}
return 0;
}
```
这个题非常水，所以我就拿了全分。~~然后非常皮的写了150行~~
B[贪心]
题意：给你一个01数组初始状态，问能否在10步内求得目标状态
我们从0的角度出发
因为0只有一种移动方式
就是在旁边有1的情况才能移动，并且只能与这个1相连的1交换。
所以0的顺序并不会调换
这样我们就可以对每个0最终处于哪个位置进行标记
首先我们知道总有一个0通过一步是可以直接到目标点的
然后这个到达目标点后，一定会有更多的能够到达位置
所以每个0到达目标位置总需要1或0步
这时我们再判断那些点的位置等于他本身就行了。
```cpp
#include<cstdio>
int n,a,b,num0,num[30],ans;
int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a);
if (a==0) num[++num0]=i;
}
ans=num0; num0=0;
for (int i=1;i<=n;i++){
scanf("%d",&b);
if (b==0)
if (num[++num0]==i) ans--;
}
if (ans<=10) printf("%d\n",ans);
else puts("QAQ");
return 0;
}
```
这个题虽然有点考思维，但也很水，所以也拿了全分。
C[二分答案+贪心]
题意：给你n个数，让你每次从中选出m个数组成一个序列，且其中后一项永远大于等于前一项的2倍，每个数只能选一次，问最多可以抠出几个序列
这个题发现答案可以二分
然后贪心
每次找出最小的序列取出
贪心是一定可行的
最后输出可行结果即可
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m,a[100010],b[100010],ans;
inline long long v_in(){
char ch=getchar();
long long sum=0;
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9'){
sum=(sum<<3)+(sum<<1)+(ch^48);
ch=getchar();
}
return sum;
}
inline bool judge(long long k){
for (long long i=0;i<k;i++) b[i]=0;
long long i=0,j=0,t=0;
while (i<k*m){
t++;
while (t<=n&&a[t]<2*b[j]) t++;
if (t>n) return false;
b[j]=a[t];
i++;
if (j==k-1) j=0;
else j++;
}
return true;
}
int main(){
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
n=v_in();
m=v_in();
for (register long long i=1;i<=n;i++) a[i]=v_in();
sort(a+1,a+n+1);
long long l=0,r=n/m;
while (l<=r){
long long mid=(l+r)>>1;
if (judge(mid)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}
```
这个题本身我只想骗个n/m的分，结果骗到了35分。
总的来说，自己其实并不是很满意，最后一题该想的没有想到。
### 2.月考是真的爆炸
我都有种想冲国家队逃避高考的冲动了。
### 3.今天是平安夜
希望自己的愿望能够实现吧。
### 4.月考结束了。
我也要开始看内容了。
首先把上个星期的暴搜看完
然后：
1.CDQ分治
2.SG函数
3.Link-Cut Tree
4.搜索剪枝(A-star,IDA-star等)
5.数论知识