A 题:
题目大意:
给出内角全为 120 度的六边形的六条边的边长,求由多少边长为 1 的等边三角形构成。
解题思路:
将六边形补全为一个大的等边三角形,则大的等边三角形的边长为六边形的相邻三边之和,接着减去补的部分。
补的部分是三个边长为认识 3 个不相邻的六边形边长的长度构成的等边三角形,边长为 a 的等边三角形,由 a*a 个边
长为 1 的小三角形构成。
代码:
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- int main()
- {
- int a[10];
- for(int i=0;i<6;i++)
- {
- scanf("%d",&a[i]);
- }
- long long cur=a[0]+a[1]+a[2];
- long long ans=cur*cur-a[0]*a[0]-a[2]*a[2]-a[4]*a[4];
- cout<<ans<<endl;
- return 0;
- }
B. Equivalent Strings
题目大意:
依据给定的规则推断字符串相等。
解题思路:
依照题意递归写就可。
代码:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- const int maxn=200000+1000;
- char s1[maxn];
- char s2[maxn];
- int judge(int st1,int en1,int st2,int en2)
- {
- int sign=0;
- for(int i=st1,j=st2;i<=en1;i++,j++)
- {
- if(s1[i]!=s2[j])
- {
- sign=1;
- break;
- }
- }
- if(sign==0)
- return 1;
- else
- {
- if((en1-st1+1)%2==0)
- {
- int mid1=st1+(en1-st1+1)/2-1;
- int mid2=st2+(en2-st2+1)/2-1;
- if(judge(st1,mid1,st2,mid2)&&judge(mid1+1,en1,mid2+1,en2))
- return 1;
- if(judge(st1,mid1,mid2+1,en2)&&judge(mid1+1,en1,st2,mid2))
- return 1;
- }
- }
- return 0;
- }
- int main()
- {
- int len1,len2;
- scanf("%s%s",s1,s2);
- len1=strlen(s1);
- len2=strlen(s2);
- if(len1!=len2)
- cout<<"NO\n"<<endl;
- else
- {
- int sign;
- sign=judge(0,len1-1,0,len1-1);
- if(sign)
- printf("YES\n");
- else
- printf("NO\n");
- }
- return 0;
- }
C. Gerald and Giant Chess
题目大意:
给定 h*w 的格子,n 个不可走的点。从 (1,1) 到(h,w)点。每次仅仅能向下或者向右。求有多少种走法?
解题思路:
首先先不考虑不可走的点,有 C(h+w-2,h-1) 种走法,一共走 h+w-2 步,向下的有 h-1 步。
接着考虑当中的不可走的
点,对于一个不可走的点 (x,y)。它走到这个的点的走法是 dp[i],它少走的是 dp[i]*C(h-x,w-y,h-x),于是把每一个不可走
的点当为终点。能够求出全部的走法数。
代码:
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- int h,w,n;
- const int maxn=200000+100;
- const int mod=1000000000+7;
- long long c[maxn];
- long long inv[maxn];
- long long dp[5000];
- struct node
- {
- int x;
- int y;
- }a[10000];
- long long pow_mod(long long a,int b)//矩阵高速幂
- {
- long long ans=1;
- while(b)
- {
- if(b&1)
- ans=(ans*a)%mod;
- a=(a*a)%mod;
- b=b/2;
- }
- return ans;
- }
- long long com(int x,int y)//求组合数C(x,y)
- {
- return ((c[x]*inv[y])%mod*inv[x-y])%mod;
- }
- bool cmp(node u,node v)
- {
- if(u.x==v.x)
- return u.y<v.y;
- return u.x<v.x;
- }
- int main()
- {
- scanf("%d%d%d",&h,&w,&n);
- for(int i=0;i<n;i++)
- scanf("%d%d",&a[i].x,&a[i].y);
- sort(a,a+n,cmp);
- long long ans=0;
- c[0]=1;
- for(int i=1;i<maxn;i++)
- c[i]=c[i-1]*i%mod;
- inv[0]=1;
- for(int i=1;i<maxn;i++)
- inv[i]=pow_mod(c[i],mod-2);//费马小定理求逆。a^(p-2)=a^(-1)
- ans=com(h+w-2,h-1);
- for(int i=0;i<n;i++)
- {
- dp[i]=com(a[i].x+a[i].y-2,a[i].x-1);
- for(int j=0;j<i;j++)//求过第i个点的方法数
- {
- if(a[j].x<=a[i].x&&a[j].y<=a[i].y)//推断能否够到达i点
- {
- dp[i]-=(dp[j]*com(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x))%mod;
- dp[i]=(dp[i]+mod)%mod;
- }
- }
- ans=(ans-(dp[i]*com(h+w-a[i].x-a[i].y,h-a[i].x))%mod+mod)%mod;
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2141900.html