这几天状态真迷，也许需要休息休息.
A. World Final? World Cup! (I)
数据量很小，把题目意思翻译一下即可.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int a=0,b=0;
string s;
cin>>s;
bool flag=false;
int a_=5,b_=5;
for(int i=0;i<10;i++)
{
if(i%2==0)
a_--;
else
b_--;
if(s[i]=='1')
{
if(i%2==0)
a++;
else
b++;
}
if(a>b+b_||a+a_<b)
{
cout<<i+1<<'\n';
flag=true;
break;
}
}
if(!flag)
cout<<-1<<'\n';
}
return 0;
}C. 现在是，学术时间 (I)
可以发现
发现每个教授一篇论文其实就是最优了.
只需要统计一下被引用0次的论文数量即可.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int a;
int ans=n;
for(int i=1;i<=n;i++)
{
cin>>a;
if(a==0)
ans--;
}
cout<<ans<<'\n';
}
return 0;
}D. 现在是，学术时间 (II)
把题读明白发现就是个签到题，分类讨论一下即可，注意输出高精度.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&-(x))
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
long double x,y,xp,yp;
cin>>x>>y>>xp>>yp;
if(xp>x)
{
if(yp>y)
{
printf("%.9Lf\n",x*y/(xp*yp));
}
else
{
printf("%.9Lf\n",max(x*yp/(x*y+xp*yp-x*yp),(y-yp)*x/(x*y+(y-yp)*(xp-x))));
}
}
else
{
if(yp>y)
{
printf("%.9Lf\n",max(xp*y/(x*y+(yp-y)*xp),(x-xp)*y/(x*y+(x-xp)*(yp-y))));
}
else
{
printf("%.9Lf\n",max(xp,x-xp)*max(yp,y-yp)/(x*y));
}
}
}
return 0;
}E. 鸡算几何
题面
题意就是一个L型铁丝ABC经合同变换变成DEF，问是否可以确定有对称的操作.
等腰的时候不能判断.
其他情况进行长度匹配，算一下叉乘的符号是否相同即可.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,double> PDD;
typedef pair<int,int> PII;
//#define lowbit(x) ((x)&-(x))
const double eps=1e-5;
double len(PDD a)
{
return a.first*a.first+a.second*a.second;
}
double cross(PDD a,PDD b)
{
return a.first*b.second-a.second*b.first;
}
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
PII A,B,C;
PDD D,E,F;
cin>>A.first>>A.second>>B.first>>B.second>>C.first>>C.second;
cin>>D.first>>D.second>>E.first>>E.second>>F.first>>F.second;
PII BA={A.first-B.first,A.second-B.second},BC={C.first-B.first,C.second-B.second};
PDD ED={D.first-E.first,D.second-E.second},EF={F.first-E.first,F.second-E.second};
if(len(BA)==len(BC))
{
cout<<"NO"<<'\n';
}
else
{
if(fabs(len(ED)-len(BA))>=eps)
swap(BA,BC);
if(cross(BA,BC)*cross(ED,EF)<0)
cout<<"YES"<<'\n';
else
cout<<"NO"<<'\n';
}
}
return 0;
}H. 本题主要考察了DFS
看了题之后发现用不到DFS.
总面积是一定的，最后只需要输出被隐藏拼图的价值，而这个价值与面积成正比，所以可以通过面积来算出答案.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500;
string s[N];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n*n-1;i++)
{
cin>>s[i];
for(int j=0;j<4;j++)
{
if(s[i][j]=='2')
ans++;
else if(s[i][j]=='1')
ans--;
}
}
cout<<10-ans<<'\n';
}
return 0;
}K. 本题主要考察了dp
题面
从小情况入手，接着对n分类讨论一下，发现100100...1111这样是最优的.
然后按这种情形记个数.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int ceil(int n,int m)
{
if(n%m==0)
return n/m;
else
return n/m+1;
}
int main() {
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
if(m<=ceil(n,3))
cout<<0<<'\n';
else
{
m-=ceil(n,3);
if(n%3==0)
{
int ans=m/2*3+(m%2==0?-1:1);
cout<<min(n-2,ans)<<'\n';
}
else if(n%3==1)
{
int ans=m/2*3+1+(m%2==0?-1:1);
cout<<min(n-2,ans)<<'\n';
}
else if(n%3==2)
{
if(m==1)
cout<<1<<'\n';
else
{
int ans=1;
m-=1;
ans+=m/2*3+1+(m%2==0?-1:1);
cout<<min(n-2,ans)<<'\n';
}
}
}
return 0;
}L. 本题主要考察了运气
竟然算出来是3.50，但过不了.
恼羞成怒下开始枚举，罚了20次过了.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cout<<32<<'\n';
return 0;
}M. 本题主要考察了找规律
数据范围不大，暴力加记忆化就可以
核心递推式
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
const int N=505;
double dp[N][N];
int main() {
ios::sync_with_stdio(false);
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=1;k<=j;k++)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k]+(double)k/(m-j+k));
}
}
}
printf("%.9lf\n",dp[n][m]);
return 0;
}