A题 先求出来这个数是第几大 阶乘求概率p 然后计算获得胜率的概率 常规解法把所有情况考虑一遍（跳1次，2次，3次……）要用到组合数 数可能太大了会爆的行不通
我们观察发现它有递推性质，从第二大开始获胜概率为Q1=p（直接跳到第一大）从第三大开始获胜概率为Q2=p*Q1(先跳到第二大）+p（直接跳到第一大）以此类推Q3=Q2*p+Q1*p+p
Q4=Q3*p+Q2*p+Q1*p+p 但是我们按照上面的递推式计算Qn时复杂度为O(n*n) 我们再改进一下Q2=Q1*(1+p)，Q3=Q2*(1+p) ，Q4=Q3*(1+p)这样复杂度就为 O(n) 了
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
using namespace std;
const int maxn = 2e2+;
const int maxm = 1e6+;
const int inf = 0x3f3f3f3f;
const double epx = 1e-;
typedef long long ll;
int a[maxn],b[maxn],c[maxn];
double f[maxm];
int main()
{
int t,n;
b[]=;
for(int i=;i<=;i++)
b[i]=b[i-]*i;
cin>>t;
while(t--)
{
cin>>n;
int cnt=;
while(n!=)
{
c[++cnt]=n%;
a[n%]++;
n/=;
}
reverse(c+,c+cnt+);
int sum=;
for(int i=;i<=cnt;i++)
{
for(int j=;j>=;j--)
{
if(a[j]>)
{
if(j>c[i])
sum+=b[cnt-i];
else if(j==c[i])
{
a[j]--;
break;
}
}
}
}
double p=1.0/b[cnt];
if(sum==)
f[]=;
else
{
f[sum-]=p;
for(int i=sum-; i>=; i--)
{
f[i]=f[i+]*p+f[i+];
}
}
printf("%.9lf\n",f[]);
}
}
B题 直接模拟 我写的是最暴力的那种。。。
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
using namespace std;
const int maxn= 2e2+;
const int maxm= 1e4+;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int main()
{
int t,n,m;
while(cin>>t)
{
while(t--)
{
char a[maxn][maxn];
char ans[maxn];
cin>>n>>m;
char x,y;
for(int i=;i<=m;i++)
{
for(int j=;j<=*n;j++)
{
cin>>a[i][j];
}
}
for(int i=;i<*n;i=i+)
{
int cnt1=,cnt2=,cnt3=,cnt4=;
int flag=;
for(int j=;j<=m;j++)
{
if(a[j][i+]=='T')
{
ans[i/+]=a[j][i];
flag=;
break;
}
else
{
if(a[j][i]=='A')
cnt1++;
else if(a[j][i]=='B')
cnt2++;
else if(a[j][i]=='C')
cnt3++;
else if(a[j][i]=='D')
cnt4++;
}
}
if(flag==)
{
if(cnt1>&&cnt2>&&cnt3>)
ans[i/+]='D';
else if(cnt1>&&cnt2>&&cnt4>)
ans[i/+]='C';
else if(cnt1>&&cnt3>&&cnt4>)
ans[i/+]='B';
else if(cnt2>&&cnt3>&&cnt4>)
ans[i/+]='A';
else
ans[i/+]='?';
}
}
for(int i=;i<=n-;i++)
printf("%c ",ans[i]);
printf("%c\n",ans[n]);
}
}
}
F题 水~~
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
using namespace std;
const int maxn= 1e3+;
const int maxm= 1e4+;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int n,m;
int a[maxn];
int main()
{
while(cin>>n)
{
int a,b;
while(n--)
{
cin>>a>>b;
if(a==b)
printf("Square\n");
else
printf("Rectangle\n");
}
}
}
I题 n比较小直接枚举组合情况 一位一位比较记录第一次和最后一次不同的位置，直接异或也可以
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
using namespace std;
const int maxn= 1e3+;
const int maxm= 1e4+;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int n,m;
int a[maxn];
int main()
{
int t;
while(cin>>t)
{
while(t--)
{
cin>>n;
for(int i=; i<=n; i++)
cin>>a[i];
sort(a+,a++n);
int ans=-;
for(int i=; i<n; i++)
{
for(int j=i+; j<=n; j++)
{
int num=;
int tempi=a[i],tempj=a[j];
int cnt=;
while(tempi!=)
{
int ki=tempi&;
int kj=tempj&;
if(ki!=kj)
{
num++;
}
tempi=tempi>>;
tempj=tempj>>;
cnt++;
}
while(tempj!=)
{
if(tempj&)
{
num++;
}
tempj=tempj>>;
cnt++;
}
//printf("%d %d %d\n",a[i],a[j],num);
ans=max(ans,num);
}
}
cout<<ans<<endl;
}
}
}