【SinGularLaRiTy-1044】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
小水塘(lagoon)
题目描述
忘川沧月的小水塘的水面是一片由以下两种图形组成的图案：
<图lagoon-1>
这两种图形都由一个边长为2的正方形和两个半径为1的1/4圆组成，圆心在正方形的两个对角顶点上。
小水塘左上角坐标为(0,0)，右下角坐标为(2*n,2*m)。水面上每一个顶点坐标为偶数的2*2正方形，都是上面两个图形中的一种。如果我们往水塘中的某个位置倒一桶污水，那么这桶污水会像画图中的油漆桶一样扩散开来，占据一片连续的区域，但是在线条边界处会停止扩散。注意如果倒在了线条上，扩散面积为0。
如下图所示，就是一个由4行4列上述图形组成的、左上角坐标(0,0)、右下角坐标(8,8)、某些位置倒了污水的水塘（白色部分为线条边界，线条实际宽度认为是0，为了明显、美观，此处加粗显示）：
<图lagoon-2>
现在给出一个n行m列的由上述两种图形组成的水塘，起初水塘中全部为净水。给定q个往某个坐标上(x,y)倾倒污水的操作，对于每次操作，请求出在(x,y)上倾倒的污水最终会扩散多大的面积。
输入格式
第一行两个整数n、m。
接下来n行每行m个整数，每个整数是0或者1，中间没有空格隔开。0代表此处是<图lagoon-1>中左侧那个2*2的图形，1代表此处是右侧那个图形。例如<图lagoon-2>中的第一行用“0001”表示。
第n+2行是一个整数q。
接下来q行每行两个用空格隔开的整数x、y，表示这一次倾倒污水的坐标。
输出格式
对于每个询问，输出此次倾倒的污水最终扩散的面积，四舍五入保留4位小数。
样例数据
| 样例输入1 | 样例输出1 |
| 1 2 0 1 4 0 0 2 0 0 1 0 2 |
0.7854 4.8584 0.0000 4.8584 |
| 样例输入2 | 样例输出2 |
| 3 1 1 0 1 2 3 1 4 2 |
7.2876 1.5708 |
<数据范围>
对于 100% 的数据，1<=n,m,q<=100，0<=x<=2*n，0<=y<=2*m。
解析
看到数据范围很小，自然地考虑用搜索。由于只有两种图案，若进行搜索，需要考虑 2*4=8 种可能的情况。需要注意的是，如图所示，污水若覆盖了A，那么污水可能覆盖了B，也可能没有覆盖B——这就意味着要把这两个区域的vis访问情况分开进行记录。（这题的if串也是没的说了）
Code
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue> using namespace std; const double pi=acos(-1.0);
const double big=-0.5*pi;
const double small=0.25*pi; int map[][];
int col[][][]={};
int list[][]; double all[]; struct P{
int x,y,k;
}now;
queue<P> q; int n,m,qq; inline void flod(int x,int y,int k,int cnt)
{
now.x=x;
now.y=y;
now.k=k;
q.push(now);
while(!q.empty())
{
now=q.front();
q.pop();
if(col[now.x][now.y][now.k])
continue;
col[now.x][now.y][now.k]=cnt;
if(now.k!=)
all[cnt]+=small;
else
all[cnt]+=big;
if(map[now.x][now.y]==)
{
if(now.k==)
{
if(now.x-)
{
if(map[now.x-][now.y]==)
q.push((P){now.x-,now.y,});
else
q.push((P){now.x-,now.y,});
}
if (now.y-)
{
if(map[now.x][now.y-]==)
q.push((P){now.x,now.y-,});
else
q.push((P){now.x,now.y-,});
}
}
if(now.k==)
{
if(now.x-)
{
if(map[now.x-][now.y]==)
q.push((P){now.x-,now.y,});
else
q.push((P){now.x-,now.y,});
}
if (now.y-)
{
if(map[now.x][now.y-]==)
q.push((P){now.x,now.y-,});
else
q.push((P){now.x,now.y-,});
}
if(now.x+<=n)
{
if(map[now.x+][now.y]==)
q.push((P){now.x+,now.y,});
else
q.push((P){now.x+,now.y,});
}
if (now.y+<=m)
{
if(map[now.x][now.y+]==)
q.push((P){now.x,now.y+,});
else
q.push((P){now.x,now.y+,});
}
}
if(now.k==)
{
if(now.x+<=n)
{
if(map[now.x+][now.y]==)
q.push((P){now.x+,now.y,});
else
q.push((P){now.x+,now.y,});
}
if(now.y+<=m)
{
if(map[now.x][now.y+]==)
q.push((P){now.x,now.y+,});
else
q.push((P){now.x,now.y+,});
}
}
}
else
{
if(now.k==)
{
if(now.x-)
{
if(map[now.x-][now.y]==)
q.push((P){now.x-,now.y,});
else
q.push((P){now.x-,now.y,});
}
if(now.y+<=m)
{
if(map[now.x][now.y+]==)
q.push((P){now.x,now.y+,});
else
q.push((P){now.x,now.y+,});
}
}
if(now.k==)
{
if(now.x-)
{
if(map[now.x-][now.y]==)
q.push((P){now.x-,now.y,});
else
q.push((P){now.x-,now.y,});
}
if(now.y-)
{
if(map[now.x][now.y-]==)
q.push((P){now.x,now.y-,});
else
q.push((P){now.x,now.y-,});
}
if(now.x+<=n)
{
if(map[now.x+][now.y]==)
q.push((P){now.x+,now.y,});
else
q.push((P){now.x+,now.y,});
}
if(now.y+<=m)
{
if(map[now.x][now.y+]==)
q.push((P){now.x,now.y+,});
else
q.push((P){now.x,now.y+,});
}
}
if(now.k==)
{
if(now.x+<=n)
{
if(map[now.x+][now.y]==)
q.push((P){now.x+,now.y,});
else
q.push((P){now.x+,now.y,});
}
if(now.y-)
{
if(map[now.x][now.y-]==)
q.push((P){now.x,now.y-,});
else
q.push((P){now.x,now.y-,});
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;++i)
for (int j=;j<=m;++j)
{
char ch;ch=getchar();
while(ch!=''&&ch!='')
ch=getchar();
map[i][j]=ch-'';
}
scanf("%d",&qq);
int cnt=;
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
for(int k=;k<=;++k)
if(!col[i][j][k])
flod(i,j,k,++cnt);
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
{
int xx=i-,yy=j-;
if (map[i][j]==)
{
list[xx*][yy*]=col[i][j][];
list[xx*+][yy*+]=col[i][j][];
list[xx*+][yy*]=col[i][j][];
list[xx*][yy*+]=col[i][j][];
list[xx*+][yy*+]=col[i][j][];
}
if (map[i][j])
{
list[xx*][yy*]=col[i][j][];
list[xx*+][yy*+]=col[i][j][];
list[xx*+][yy*+]=col[i][j][];
list[xx*+][yy*]=col[i][j][];
list[xx*][yy*+]=col[i][j][];
}
}
while (qq--)
{
int x,y;
scanf("%d%d",&x,&y);
if((x%)!=(y%))
{
printf("0.0000\n");
continue;
}
printf("%.4f\n",all[list[x][y]]);
}
}
颂芬梭哈(ptgiving)
题目描述
Alice 和 Mukyu 最近偶然得到了一本写有一种叫做梭哈的扑克游戏的规则的说明书（名为《C████████nd》，中间部分被涂掉了），据其所述，梭哈是一种使用黑桃、红心、梅花、方片的 A 到 K 共 52 张牌(没有大小王）来进行的扑克牌游戏。
不幸的是，规则说明中有关整个游戏的进行方式的部分被撕掉了，Alice 和 Mukyu 从残存的部分只得知了“手牌上限是 5 张”这一消息，所以他们决定每次直接给两人各发 5 张牌，判定谁的手牌比较大，说明书中关于手牌大小判定的信息如下：
“
所有五张牌的组合，按以下秩序，由大至小排行分为不同牌型：
1、同花顺（Straight Flush）：同一花色，顺序的牌。 例： Q♦ J♦ 10♦ 9♦ 8♦；
2、四条（Four of a Kind）：有四张同一点数的牌。 例： 10♣ 10♦ 10♥ 10♠ 9♥；
3、满堂红（Full House）：三张同一点数的牌，加一对其他点数的牌。 例： 8♣ 8♦ 8♠ K♥ K♠；
4、同花（Flush）：五张同一花色的牌。 例： A♠ K♠ 10♠ 9♠ 8♠；
5、顺子（Straight）：五张顺连的牌。 例： K♦ Q♥ J♠ 10♦ 9♦；
6、三条（Three of a kind）：有三张同一点数的牌。 例： J♣ J♥ J♠ K♦ 9♠；
7、两对（Two Pairs）：两张相同点数的牌，加另外两张相同点数的牌。 例： A♣ A♦ 8♥ 8♠ Q♠；
8、一对（One Pair）：两张相同点数的牌。 例： 9♥ 9♠ A♣ J♠ 8♥；
9、无对（Zilch）：不能排成以上组合的牌，以点数决定大小。例： A♦ Q♦ J♠ 9♣ 8♣。
若牌型一样则利用点数和花色决定胜负。（点数优先）
点数的顺序（从大至小）为：A>K>Q>J>10>9>8>7>6>5>4>3>2。（注：当 5 张手牌是 5
4 3 2 A 的时候，A 可以看作最小的牌，此时的牌型仍然为顺子，是顺子里面最小的一个）。
花色的顺序（大至小）为：黑桃(♠)>红心(♥)>梅花(♣)>方块(♦)。
举例说明：
1、Q♦ J♦ 10♦ 9♦ 8♦ > 8♣ 8♥ 8♠ K♥ K♠ （前者牌型为同花顺，比后者大）；
2、9♣ 9♦ 9♠ Q♥ Q♠ > 8♣ 8♦ 8♠ K♥ K♠ （两者牌型均为满堂红，比较牌型中三张同一点数的牌 9 比 8 大）；
3、A♣ A♦ 8♥ 8♠ Q♠ > A♠ A♥ 7♥ 7♠ K♠ （两者牌型均为两对，且最大的对子相同，此时比较次大的对子，8 比 7 大）；
4、A♠ Q♠ J♥ 9♥ 8♥ > A♦ Q♦ J♠ 9♣ 8♣ （两者牌型均为无对，所有数码均相同，此时比较最大牌的花色，A♠ > A♦）。
5、4♠ 4♥ A♦ Q♦ 5♦ > 4♣ 4♦ A♠ Q♠ 5♠ （两者牌型均为一对，所有数码均相同，此时对 4 为牌型里最大的部分，因此比较 4♠ > 4♣）
”
尽管 Alice 和 Mukyu 都可以轻易的判断出结果，他们还是想见识一下现代科技的力量。
输入格式
第一行包含一个正整数 N，表示有 N 组测试数据。
每组测试数据包含 10 行，前 5 行每行用两个整数描述一张 Alice 手上的牌，第一个数表示牌的数码（1 表示 A，13 表示 K），第二个数表示牌的花色（1 表示黑桃，2 表示红心， 3 表示梅花，4 表示方块）。
后 5 行每行用两个整数描述 Mukyu 手上的牌，格式同上。
输出格式
对于每组测试数据，在单独的一行内输出 Alice 或 Mukyu，表示谁能赢。
样例数据
| 样例输入 | 样例输出 |
|
1 |
Alice |
<样例解释>
Alice 的手牌构成同花顺，而 Mukyu 的手牌仅构成普通顺子。
<数据范围>
对于 10%的数据，保证输入的全部牌型都是无对。
对于另外 30%的数据，保证输入的全部牌型都是顺子、同花或同花顺。
对于 100%的数据，保证 N ≤ 100000。
C++选手如果使用 cin 读入数据很可能因此超时，推荐使用 scanf/printf。
解析
模拟：一大堆 if串+函数 考虑每一种牌型比较的情况。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> #define num first
#define col second
#define mp make_pair using namespace std; typedef pair<int,int> pii;
const int N=+; int cnt[]; inline void getint(int&num){
char c;num=;
while((c=getchar())<''||c>'');
while(c>=''&&c<=''){num=num*+c-;c=getchar();}
} int T;pii Ail[N],Muk[N];
bool cmp(pii a,pii b){
if(a.num==b.num)
return a.col>b.col;
else return a.num<b.num;
}
bool isone(pii *arr){//同花顺
memset(cnt,,sizeof cnt);
for(int i=;i<=;i++){
if(arr[i].col!=arr[].col)
return ;
cnt[arr[i].num]++;
if(arr[i].num==)
cnt[]++;
}
for(int i=;i<=;i++)
if(cnt[i]==&&cnt[i+]==&&cnt[i+]==&&cnt[i+]==&&cnt[i+]==)
return ;
return ;
}
bool istwo(pii *arr){//四条
bool f=;
for(int i=;i<=;i++)
if(arr[i].num!=arr[].num){
f=;break ;
}
if(f) return ;
f=;
for(int i=;i<=;i++)
if(arr[i].num!=arr[].num){
f=;break ;
}
return f;
}
bool isthree(pii *arr){//满堂红
if(arr[].num==arr[].num&&arr[].num==arr[].num&&arr[].num==arr[].num)
return ;
if(arr[].num==arr[].num&&arr[].num==arr[].num&&arr[].num==arr[].num)
return ;
return ;
}
bool isfour(pii *arr){//同花
for(int i=;i<=;i++)
if(arr[i].col!=arr[].col)
return ;
return ;
}
bool isfive(pii *arr){//顺子
memset(cnt,,sizeof cnt);
for(int i=;i<=;i++){
cnt[arr[i].num]++;
if(arr[i].num==)
cnt[]++;
}
for(int i=;i<=;i++)
if(cnt[i]==&&cnt[i+]==&&cnt[i+]==&&cnt[i+]==&&cnt[i+]==)
return ;
return ;
}
bool issix(pii *arr){//三条
if(arr[].num==arr[].num&&arr[].num==arr[].num)
return ;
if(arr[].num==arr[].num&&arr[].num==arr[].num)
return ;
if(arr[].num==arr[].num&&arr[].num==arr[].num)
return ;
return ;
}
bool isseven(pii *arr){//两对
memset(cnt,,sizeof cnt);
for(int i=;i<=;i++)
cnt[arr[i].num]++;
int tot=;
for(int i=;i<=;i++)
if(cnt[i]==) tot++;
return tot==;
}
bool iseight(pii *arr){//一对
for(int i=;i<=;i++)
if(arr[i].num==arr[i-].num)
return ;
return ;
}
int check(pii *arr){
if(isone(arr)) return ;
else if(istwo(arr)) return ;
else if(isthree(arr)) return ;
else if(isfour(arr)) return ;
else if(isfive(arr)) return ;
else if(issix(arr)) return ;
else if(isseven(arr)) return ;
else if(iseight(arr)) return ;
else return ;
}
bool cmp1(pii *a,pii *b){//同花顺
bool f1=,f2=;
if(a[].num==&&a[].num==) f1=;
else if(b[].num==&&b[].num==) f2=;
if(f1!=f2) return f1;
if(f1&&f2) return a[].col<b[].col; if(a[].num==b[].num)
return a[].col<b[].col;
else return a[].num>b[].num;
}
bool cmp2(pii *a,pii *b){//四条
int num_a1,num_a2,col_a;
if(a[].num==a[].num&&a[].num==a[].num&&a[].num==a[].num){
num_a1=a[].num,num_a2=a[].num;
col_a=a[].col;
}
else{
num_a1=a[].num,num_a2=a[].num;
col_a=a[].col;
} int num_b1,num_b2,col_b;
if(b[].num==b[].num&&b[].num==b[].num&&b[].num==b[].num){
num_b1=b[].num,num_b2=b[].num;
col_b=b[].col;
}
else{
num_b1=b[].num,num_b2=b[].num;
col_b=b[].col;
} if(num_a1==) num_a1=;
if(num_a2==) num_a2=;
if(num_b1==) num_b1=;
if(num_b2==) num_b2=; if(num_a1!=num_b1)
return num_a1>num_b1;
else{
if(num_a2!=num_b2)
return num_a2>num_b2;
else return col_a<col_b;
}
}
bool cmp3(pii *a,pii *b){//满堂红
for(int i=;i<=;i++)
if(a[i].num==) a[i].num=;
for(int i=;i<=;i++)
if(b[i].num==) b[i].num=;
sort(a+,a+,cmp);
sort(b+,b+,cmp); int sta1,sta2,stb1,stb2;
if(a[].num==a[].num&&a[].num==a[].num)
sta1=,sta2=;
else sta1=,sta2=; if(b[].num==b[].num&&b[].num==b[].num)
stb1=,stb2=;
else stb1=,stb2=; for(int i=sta1+,j=stb1+;i>=sta1&&j>=stb1;i--,j--){
if(a[i].num==b[j].num) continue ;
else return a[i].num>b[j].num;
} for(int i=sta2+,j=stb2+;i>=sta2&&j>=stb2;i--,j--){
if(a[i].num==) a[i].num=;
if(b[j].num==) b[j].num=;
else if(a[i].num==b[j].num) continue ;
else return a[i].num>b[j].num;
} for(int i=sta1+,j=stb1+;i>=sta1&&j>=stb1;i--,j--){
if(a[i].col==b[j].col) continue ;
else return a[i].col<b[i].col;
} for(int i=sta2+,j=stb2+;i>=sta2&&j>=stb2;i--,j--){
if(a[i].col==b[j].col) continue ;
else return a[i].col<b[i].col;
} return ;
}
bool cmp4(pii *a,pii *b){//同花
for(int i=;i<=;i++)
if(a[i].num==) a[i].num=;
for(int i=;i<=;i++)
if(b[i].num==) b[i].num=;
sort(a+,a+,cmp);
sort(b+,b+,cmp);
for(int i=;i;i--){
if(a[i].num==b[i].num) continue ;
return a[i].num>b[i].num;
}
for(int i=;i;i--){
if(a[i].col==b[i].col) continue ;
return a[i].col<b[i].col;
}
return ;
}
bool cmp5(pii *a,pii *b){//顺子
if(a[].num==&&a[].num==){
pii t=a[];t.num=;
for(int i=;i<=;i++)
a[i-]=a[i];
a[]=t;
}
if(b[].num==&&b[].num==){
pii t=b[];t.num=;
for(int i=;i<=;i++)
b[i-]=b[i];
b[]=t;
}
/*for(int i=5;i;i--){
if(a[i].num==b[i].num) continue ;
return a[i].num>b[i].num;
}*/
if(a[].num!=b[].num)
return a[].num>b[].num;
for(int i=;i;i--){
if(a[i].col==b[i].col) continue ;
return a[i].col<b[i].col;
}
return ;
}
bool cmp6(pii *a,pii *b){//三条
for(int i=;i<=;i++)
if(a[i].num==) a[i].num=;
for(int i=;i<=;i++)
if(b[i].num==) b[i].num=;
sort(a+,a+,cmp);
sort(b+,b+,cmp); int sta;
for(int i=;i<=;i++)
if(a[i].num==a[i-].num&&a[i].num==a[i-].num){
sta=i-;break ;
} int stb;
for(int i=;i<=;i++)
if(b[i].num==b[i-].num&&b[i].num==b[i-].num){
stb=i-;break ;
} for(int i=sta+,j=stb+;i>=sta&&j>=stb;i--,j--){
if(a[i].num==b[j].num) continue ;
else return a[i].num>b[j].num;
} for(int i=,j=;i&&j;i--,j--){
if(i==sta+) i=sta-;
if(j==stb+) j=stb-;
if(a[i].num==b[j].num) continue ;
else return a[i].num>b[j].num;
} for(int i=sta+,j=stb+;i>=sta&&j>=stb;i--,j--){
//printf("%d %d\n",a[i].col,b[j].col);
if(a[i].col==b[j].col) continue ;
else return a[i].col<b[j].col;
} for(int i=,j=;i&&j;i--,j--){
if(i==sta+) i=sta-;
if(j==stb+) j=stb-;
if(a[i].col==b[j].col) continue ;
else return a[i].col<b[j].col;
}
return ; }
bool cmp7(pii *a,pii *b){//两对
for(int i=;i<=;i++)
if(a[i].num==) a[i].num=;
for(int i=;i<=;i++)
if(b[i].num==) b[i].num=;
sort(a+,a+,cmp);
sort(b+,b+,cmp); pii pa1[],pa2[],pb1[],pb2[];
bool f1=,f2=;
bool v1[],v2[];
memset(v1,,sizeof v1);
memset(v2,,sizeof v2);
for(int i=;i<=;i++){
if(a[i].num==a[i-].num){
if(f1) pa1[]=a[i],pa1[]=a[i-];
else pa2[]=a[i],pa2[]=a[i-],f1=;
v1[i]=v1[i-]=;
} if(b[i].num==b[i-].num){
if(f2) pb1[]=b[i],pb1[]=b[i-];
else pb2[]=b[i],pb2[]=b[i-],f2=;
v2[i]=v2[i-]=;
}
}
if(pa1[].num!=pb1[].num)
return pa1[].num>pb1[].num; if(pa1[].num!=pb1[].num)
return pa1[].num>pb1[].num; if(pa2[].num!=pb2[].num)
return pa2[].num>pb2[].num; if(pa2[].num!=pb2[].num)
return pa2[].num>pb2[].num; for(int i=;i<=;i++)if(!v1[i])
for(int j=;j<=;j++)if(!v2[j]){
if(a[i].num!=b[j].num)
return a[i].num>b[j].num;
break ;
} if(pa1[].col!=pb1[].col)
return pa1[].col<pb1[].col; if(pa1[].col!=pb1[].col)
return pa1[].col<pb1[].col; if(pa2[].col!=pb2[].col)
return pa2[].col<pb2[].col; if(pa2[].col!=pb2[].col)
return pa2[].col<pb2[].col; for(int i=;i<=;i++)if(!v1[i])
for(int j=;j<=;j++)if(!v2[j]){
if(a[i].col!=b[j].col)
return a[i].col<b[j].col;
break ;
}
return ;
}
bool cmp8(pii *a,pii *b){//一对
for(int i=;i<=;i++)
if(a[i].num==) a[i].num=;
for(int i=;i<=;i++)
if(b[i].num==) b[i].num=;
sort(a+,a+,cmp);
sort(b+,b+,cmp); int sta;
for(int i=;i<=;i++)
if(a[i].num==a[i-].num){
sta=i-;break ;
} int stb;
for(int i=;i<=;i++)
if(b[i].num==b[i-].num){
stb=i-;break ;
} for(int i=sta+,j=stb+;i>=sta&&j>=stb;i--,j--){
if(a[i].num==b[j].num) continue ;
else return a[i].num>b[j].num;
} for(int i=,j=;i&&j;i--,j--){
if(i==sta+) i=sta-;
if(j==stb+) j=stb-;
if(a[i].num==b[j].num) continue ;
else return a[i].num>b[j].num;
} for(int i=sta+,j=stb+;i>=sta&&j>=stb;i--,j--){
//printf("%d %d\n",a[i].col,b[j].col);
if(a[i].col==b[j].col) continue ;
else return a[i].col<b[j].col;
} for(int i=,j=;i&&j;i--,j--){
if(i==sta+) i=sta-;
if(j==stb+) j=stb-;
if(a[i].col==b[j].col) continue ;
else return a[i].col<b[j].col;
}
return ;
}
bool cmp9(pii *a,pii *b){//无对
if(a[].num==){
pii t=a[];t.num=;
for(int i=;i<=;i++)
a[i-]=a[i];
a[]=t;
}
if(b[].num==){
pii t=b[];t.num=;
for(int i=;i<=;i++)
b[i-]=b[i];
b[]=t;
}
for(int i=;i;i--){
if(a[i].num==b[i].num) continue ;
else return a[i].num>b[i].num;
}
for(int i=;i;i--){
if(a[i].col==b[i].col) continue ;
else return a[i].col<b[i].col;
}
return ;
}
int main(){
getint(T);
while(T--){
for(int i=;i<=;i++)
getint(Ail[i].num),getint(Ail[i].col);
for(int i=;i<=;i++)
getint(Muk[i].num),getint(Muk[i].col);
sort(Ail+,Ail+,cmp);
sort(Muk+,Muk+,cmp);
int t1=check(Ail);
int t2=check(Muk);
if(t1==t2){
bool win;
if(t1==) win=cmp1(Ail,Muk);
else if(t1==) win=cmp2(Ail,Muk);
else if(t1==) win=cmp3(Ail,Muk);
else if(t1==) win=cmp4(Ail,Muk);
else if(t1==) win=cmp5(Ail,Muk);
else if(t1==) win=cmp6(Ail,Muk);
else if(t1==) win=cmp7(Ail,Muk);
else if(t1==) win=cmp8(Ail,Muk);
else if(t1==) win=cmp9(Ail,Muk);
printf("%s\n",win?"Alice":"Mukyu");
}
else printf("%s\n",t1<t2?"Alice":"Mukyu");
}
}
周年纪念(anniversary)
题目描述
距离著名意大利数学家 Fibonacci 的 900 年诞辰纪念日还剩下不到 60 年。当然，这种重要的纪念日需要很多准备。
Sidepi 认为应当解决以下问题来表达对 Fibonacci 的纪念：给定由 l、l+1、l+2……r 这 r-l+1 个整数构成的集合 A，考虑 A 的所有含有 k 个元素的子集；对于每个子集 B，设 Bi 是 能整除子集中全部 k 个元素的最大整数；i 是所有 Bi 的最大值，求第 i 个 Fibonacci 数 F[i] 是多少。 当然，Sidepi 也没忘记提醒你，F[1]=1，F[2]=1，F[n]=F[n-1]+F[n-2](n>=3)。 Sidepi 有半个多世纪的时间来解决这个问题，但是你只有 3 个半小时。因此你只需要输出 F[i] mod m 的值。
输入格式
四个用空格隔开的整数 m、l、r、k。
输出格式
上述问题的答案 F[i] mod m 的值。
样例数据
| 样例输入 | 样例输出 |
| 10 1 8 2 | 3 |
<数据范围>
对于 50% 的数据，1<=l,r<=10^6；对于 100% 的数据，1<=m<=10^9，1 ≤ l < r ≤ 10^12，2 ≤ k ≤ r - l + 1。
解析
[l,r]间i的倍数的个数等于r/i-(l-1)/i，随着i的增大r/i是减小的，(l-1)/i也是减小的，通过感觉我们知道r/i-(l-1)/i大体上也是减小的，但并不是严格递减，即使用二分+暴力也不能很有效地减小这个范围
注意到从1开始一个个地枚举i是很不明智的，因为即使i++也很有可能不会使r/i和(l-1)/i中任意一项的值改变
所以可以想到对于i来说min(l/(l/i),r/(r/i))是在保证r/i和(l-1)/i不变前提下的更优值，所以我们每次都只用枚举r/i和(l-1)/i一定时i的最优值即可，然后i++如此往复计算出下一个状态的最优值，可以证明在这个过程中我们一定会遍历到使r/i-(l-1)/i>=k成立最大的那个i
这个做法很容易想出来，但是时间复杂度怎么保证呢……
不妨假设在最gg的情况l=r=1e12,k=1
那么i=1,2,3……r/3,r/2,r
注意由于i只能为整数，所以i在一开始是很连续的，但是往后开始就不连续了，我们只要把这个临界点计算出来，然后就可以分段计算出时间复杂度了。
我们可以假设第x次以及以后的分割都是按间隔为1均匀地分布的。
n/x-n/(x-1)=1
n*(x+1)=x*(x+1)+n*x
n=x*(x+1)
x=sqrt(n)
时间复杂度：O(2*sqrt(n))
Code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath> using namespace std; typedef long long ll; struct Mat{
ll s[][];
ll* operator [](const ll a){
return s[a];
}
};
Mat cv={,,,};
Mat fib={,,,}; ll m,l,r,w,x=,y;
Mat mul(Mat a,Mat b)
{
Mat s={,,,};
for(ll i=;i<;i++)
for(ll j=;j<;j++)
for(ll k=;k<;k++)
s[i][j]+=a[i][k]*b[k][j]%m;
return s;
}
Mat power(Mat a,ll b)
{
Mat s={,,,};
while(b)
{
if(b&)
s=mul(s,a);
a=mul(a,a);
b/=;
}
return s;
}
int main()
{
cin>>m>>l>>r>>w;
l--;
while(x<=r)
{
if((l/x)==)
x=r/(r/x);
else
x=min(l/(l/x),r/(r/x));
if(r/x-l/x>=w)
y=x;
x++;
}
cv=power(cv,y);
fib=mul(fib,cv);
cout<<fib[][]<<endl;
return ;
}
Time: 2017-10-29