T1 apple
【问题描述】
陶陶家门前有一块 n 行 m 列的耕地
有些格子可以种苹果(用 1 表示)，一些无法种苹果(用 0 表示)，并且相邻格子无法都种苹果
陶陶想知道有多少种种植方案(一颗也不种也是可以的)
【输入文件】
输入文件为 apple.in
第一行包含用空格隔开的两个整数 n,m
接下来 n 行每行 m 个数，为1或0，表示能否种植
【输出文件】
输出文件为 apple.out
共一行，一个整数ans，表示方案数。
【输入样例1】
1 5 1 1 1 1 1
【输出样例1】
13
【输入样例2】
1 10 1 1 1 1 0 1 1 0 1 1
【输出样例2】
72
【输入样例3】
2 10 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 0
【输出样例3】
1305
【数据规模和约定】
对于前 30%的数据,满足 n=1,所有格子都能种苹果。
对于另外 20%的数据，满足 n=1。
对于另外 20%的数据，保证每行只有一个位置能种苹果。
对于 100%的数据,满足 n<=2,m<=10
60分代码
1 #include<cstdio> 2 using namespace std; 3 const int MAXN=2,MAXM=10; 4 int n,m,a[MAXN][MAXM],ans; 5 bool b[MAXN+2][MAXM+2]; 6 int ct[11]={1,2,3,5,8,13,21,34,55,89,144}; 7 int main() 8 { 9 freopen("apple.in","r",stdin); 10 freopen("apple.out","w",stdout); 11 scanf("%d%d",&n,&m); 12 for(int i=1;i<=n;i++) 13 for(int j=1;j<=m;j++) 14 scanf("%d",&a[i][j]); 15 if(n==1)//n=1 16 { 17 for(int i=1;i<=m;i++) 18 ans=1; 19 for(int i=1,j=0;i<=m+1;i++) 20 { 21 if(a[1][i]==0) 22 { 23 ans*=ct[j]; 24 j=0; 25 } 26 else 27 { 28 j++; 29 } 30 } 31 printf("%d",ans); 32 return 0; 33 } 34 else//n==2 35 { 36 int pos; 37 for(int i=1;i<=m;i++) 38 if(a[1][i]==1) 39 pos=i; 40 if(a[2][pos]==1) 41 { 42 printf("3"); 43 return 0; 44 } 45 else 46 { 47 printf("4"); 48 return 0; 49 } 50 51 } 52 return 0; 53 }
//不知道为什么9个1过不了，不然就70分
思路:
当n=1,全部为1时,找规律可得为斐波那契数列,故记录ct[]为斐波那契数直接调用
当n=1,不全为1时,以0拆分为若干段,每段的情况相乘即为答案
当每行只有一个位置有苹果时,判断是否在同一列,在同一列答案为3,否则答案为4
理论上能骗到70分
AC代码
1 //二进制模拟 2 #include<string.h> 3 #include<iostream> 4 using namespace std; 5 #define rep(i,h,t) for (int i=h;i<=t;i++) 6 #define me(x) memset(x,0,sizeof(x)) 7 int a[30][30],p[30][30],n,m; 8 int main() 9 { 10 freopen("apple.in","r",stdin); 11 freopen("apple.out","w",stdout); 12 ios::sync_with_stdio(false);//加速cin,cout 13 cin>>n>>m; 14 int num=0; 15 rep(i,1,n) 16 rep(j,1,m) 17 { 18 cin>>a[i][j]; 19 if (a[i][j]) num++;//统计可种植点数 20 } 21 int ans=0; 22 rep(i,0,(1<<num)-1)//从num个0模拟到num个1 23 { 24 me(p);//重置种植情况 25 rep(j,1,num)//num个点的种植情况存入p数组 26 { 27 int k=(i>>(j-1))&1;//取第j位 28 int cnt=0,i1,j1; 29 for (i1=1;i1<=n;i1++) 30 { 31 for (j1=1;j1<=m;j1++) 32 { 33 if (a[i1][j1]) cnt++; 34 if (cnt==j) break;//找到第cnt个点的坐标i1,j1时跳出 35 } 36 if (cnt==j) break; 37 } 38 p[i1][j1]=k;//种植情况存入 39 } 40 bool tt=1;//初始设为合法 41 rep(i,1,n) 42 rep(j,1,m) 43 { 44 if (j>1&&p[i][j]&&p[i][j-1]) tt=0;//横向判断非法 45 if (i>1&&p[i][j]&&p[i-1][j]) tt=0;//纵向判断非法 46 if (!tt) break;//非法即跳出 47 } 48 if (tt) ans++;//合法则记录 49 } 50 cout<<ans<<endl; 51 return 0; 52 } 53 //时间复杂度:O(2^(n*m))<=2^20≈2e7
T2 music
【问题描述】
一共唱 n 个音符，每个音符持续 b[i]个时间。 比如第一个音符，在 0~b[1]-1 时间内歌唱。 比如第二个音符，在 b[1]~b[1]+b[2]-1 时间内歌唱。 以此类推。。。
现在有 q 组询问，每组询问有一个时刻 t。
求对于每一个询问 t,赤羽所唱的音符。
【输入文件】
输入文件为 music.in。
第一行两个整数 n，q。
第2~n+1行 n 个数表示每个音符持续的时间。
【输出文件】
输出文件为 music.out。 共n行。 每行输出对应的音符
【输入样例1】
3 5 2 1 3 2 3 4 0 1
【输出样例1】
2 3 3 1 1
【数据规模和约定】
对于 30%的数据 n<=1000,b[i]<=1000,q=1
另外 30%的数据 n<=1000,b[i]<=10000,q<=10000
对于 100%的数据 n<=10000,b[i]<=10000,q<=1e5
AC代码
#include<cstdio> #include<algorithm> const int MAXN=10000,MAXQ=1e5; int n,q,b[MAXN+2],a[MAXN+2]; using namespace std; int main() { freopen("music.in","r",stdin); freopen("music.out","w",stdout); scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) { scanf("%d",&b[i]); a[i]=a[i-1]+b[i];//唱完第i个音符结束的时间 if(i==1) a[i]--; } for(int i=1;i<=q;i++) { int ask; scanf("%d",&ask); int pos=lower_bound(a+1,a+n+1,ask)-a; printf("%d ",pos); } }
//STL直接带舒服
total:160/rank:1