A. 丁神去谷歌
注意将除法改成交叉相乘
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
const int MAXN=10000000000;
int n;
int main()
{
long long T,ma,mb,num=0;
read(T);
while(T--)
{
int a,b;
read(n);
read(ma),read(mb),num=1;
for(int i=1;i<n;i++)
{
read(a);read(b);
if(b*ma>a*mb)
{
ma=a;
mb=b;
num=i+1;
}
else if(b*ma==a*mb&&ma>a)
{
ma=a;
mb=b;
num=i+1;
}
else if(b*ma==a*mb&&ma==a&&num>i+1)
{
ma=a;
mb=b;
num=i+1;
}
}
printf("%lld\n",num);
}
return 0;
}
B. 丁神又去谷歌
裸01背包
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
//-------------------------------------------------------------------
typedef long long ll;
struct Node
{
int ti,w;
}a[110];
int n,t;
ll dp[110][1010];
int main()
{
int T;
read(T);
while(T--)
{
memset(dp,0,sizeof(dp));
read(t);read(n);
for(int i=1;i<=n;i++)
{
read(a[i].ti);read(a[i].w);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=t;j++)
{
dp[i][j]=dp[i-1][j];
if(a[i].ti<=j)
dp[i][j]=max(dp[i-1][j-a[i].ti]+a[i].w,dp[i][j]);
}
}
printf("%lld\n",dp[n][t]);
}
return 0;
}
C. goblin
数学题，排列组合。 首先，我们注意到这道题的某些公式，取模时候的除法，因为p不一定是质数，所以不一定能够用费马小定理求出逆元，因此一定要改变方法。 其次，我们可以发现这题是要求波浪数的个数，这种时候我比较推荐大家打表找规律，如形如/\/\/\/\/\（下称为A型）或者\/\/\/\/\/\/（下称为B型）的数字，当数字位数相同的时候，我们可以得知，A型数和B型数的个数是 相同的，这一点我们可以通过逆序数证明，大家可以去百度一下证明方法。 那么，我们就可以将某些除以二的公式给略加改进
g[i]表示的是A型（也可以是B型，但只能是其中一个）的波浪数个数，用组合数学的 插入法求出递推公式，注意，此时的g[i]只能当做一种类型来使用，因此每次记录都是j+=2的情况。
另外，如果数组都用long long 型，内存会爆，如果计算过程不用long long ，数据会爆。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define eps 1e-8
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
//-------------------------------------------------------------------
const int MAXN=4300;
int n,p;
int g[MAXN];
int c[MAXN][MAXN];
int main()
{
// freopen("data.txt","r",stdin);
while(read(n)&&read(p))
{
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
c[i][0]=1;
c[1][1]=1;
for(int i=2;i<=n;i++)
{
c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]%p+c[i-1][j]%p)%p;
}
g[0]=1%p;g[1]=1%p;g[2]=1%p;g[3]=2%p;
for(int i=4;i<=n;i++)
for(int j=0;j<=i-1;j+=2)
g[i]=(g[i]+((long long)c[i-1][j]%p*(long long)g[j]%p*(long long)g[i-1-j])%p)%p;
g[n]=(g[n]*2)%p;
/* int ans=0;
for(int i=0;i<n;i++)
a[i]=i+1;
do
{
int i;
for(i=1;i<n-1;i++)
{
if(a[i]>a[i-1]&&a[i]>a[i+1])
continue;
else if(a[i]<a[i-1]&&a[i]<a[i+1])
continue;
break;
}
if(i==n-1)
ans++;
}while(next_permutation(a,a+n));
cout<<n<<" : "<<ans<<endl;*/
cout<<g[n]<<endl;
}
return 0;
}
D. 学姐逗学弟
裸的EVERY SG 自己去看看模板或者解法吧.......
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
//-------------------------------------------------------------------
const int MAXN=100010;
int n,m;
vector<int> a[MAXN];
int sg[MAXN],po[MAXN];
bool mex[MAXN];
int step[MAXN];
void dfs(int x)
{
if(sg[x]!=-1)
return;
int sz=a[x].size(),maxx=-1*MAXN,minn=MAXN;
for(int i=0;i<sz;i++)
{
dfs(a[x][i]);
if(sg[a[x][i]]==0)
maxx=max(maxx,step[a[x][i]]);
minn=min(minn,step[a[x][i]]);
}
memset(mex,0,sizeof(bool)*(sz+10));
for(int i=0;i<sz;i++)
mex[sg[a[x][i]]]=true;
for(int i=0;i<sz+1;i++)
if(!mex[i])
{
sg[x]=i;
break;
}
if(sg[x]==0)
step[x]=minn+1;
else
step[x]=maxx+1;
if(sz==0)
step[x]=0;
// cout<<x<<" :"<<sg[x]<<endl;
}
void init()
{
for(int i=0;i<MAXN;i++)
a[i].clear();
memset(sg,-1,sizeof(sg));
memset(po,0,sizeof(po));
memset(step,0,sizeof(step));
}
int main()
{
int T;
read(T);
while(T--)
{
read(n);read(m);
init();
for(int i=2;i<=n;i++)
{
int temp;
read(temp);
a[temp].push_back(i);
}
for(int i=0;i<m;i++)
read(po[i]);
dfs(1);
int ans=-1;
for(int i=0;i<m;i++)
{
ans=max(step[po[i]],ans);//cout<<step[po[i]]<<" ";
}// cout<<endl;
if(!(ans&1))
puts("So sad...");
else
puts("MengMengDa!");
}
return 0;
}
E. 木头人足球赛
计算几何 大尧神代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
//#define LOCAL
using namespace std;
struct point
{
double x,y,d,AngleUp,AngleDown;
}Luke[20];
struct PP
{
double x,y;
}UnCovered[20];
const double eps=1e-7;
const double pi=acos(-1.0);
double xo,yo,AngleUp,AngleDown;
int negativecnt;
bool flag;
bool GetLukeAngle(int x)
{
int i;
double d=sqrt((xo-Luke[x].x)*(xo-Luke[x].x)+(yo-Luke[x].y)*(yo-Luke[x].y));
//printf("d=%lf\n",d);
if(abs(Luke[x].d-d)<eps)return false;
double a=asin(Luke[x].d/d),b;
//printf("a=%lf\n",a);
double dy=Luke[x].y-yo,dx=Luke[x].x-xo;
//printf("dy=%lf dx=%lf\n",dy,dx);
b=atan2(dy,dx);
//printf("b=%lf\n",b);
if(b>eps)b=3*pi/2-b;
else if(b<-eps)b=-pi/2-b;
else b=pi*3/2;
Luke[x].AngleDown=b-a;
Luke[x].AngleUp=b+a;
//printf("Luke[%d].Angledown=%lf Luke[%d].AngleUp=%lf\n",x,Luke[x].AngleDown,x,Luke[x].AngleUp);
return true;
}
bool cmp(const point &a,const point &b)
{
if(abs(a.AngleDown-b.AngleDown)<eps)return a.AngleUp+eps<b.AngleUp;
return a.AngleDown+eps<b.AngleDown;
}
void Init()
{
scanf("%lf%lf",&xo,&yo);//printf("xo=%lf yo=%lf\n",xo,yo);//cout<<xo<<' '<<yo<<endl;
AngleUp=atan2(38.000-yo,-xo);
if(AngleUp<-eps)AngleUp=-AngleUp-pi/2;
else if(AngleUp>eps) AngleUp=pi*3/2-AngleUp;
AngleDown=atan2(30.000-yo,-xo);
if(AngleDown<-eps)AngleDown=-AngleDown-pi/2;
else if(AngleDown>eps) AngleDown=pi*3/2-AngleDown;
//printf("Angledown=%lf AngleUp=%lf\n",AngleDown,AngleUp);
//cout<<AngleDown<<' '<<AngleUp<<endl;
flag=true;
for(int i=1;i<=11;i++)
{
scanf("%lf %lf %lf",&Luke[i].x,&Luke[i].y,&Luke[i].d);
if(flag==true)flag=GetLukeAngle(i);
}
//cout<<flag<<endl;
}
void Solve()
{
sort(Luke+1,Luke+1+11,cmp);//for(int i=1;i<=11;i++)printf("Luke[%d].Angledown=%lf Luke[%d].AngleUp=%lf\n",i,Luke[i].AngleDown,i,Luke[i].AngleUp);
//for(int i=1;i<=11;i++)printf("Luke[%d].Angledown=%lf Luke[%d].AngleUp=%lf\n",i,Luke[i].AngleDown,i,Luke[i].AngleUp);
flag=false;
double start=AngleDown;
for(int i=1;i<=11;i++)
{
if(Luke[i].AngleUp+eps<AngleDown)continue;
if(Luke[i].AngleDown>AngleUp+eps)continue;
if(Luke[i].AngleDown>start+eps)
{
flag=true;break;
}
else if(Luke[i].AngleUp>start+eps)start=Luke[i].AngleUp;
}
if(flag==false&&start+eps<AngleUp)flag=true;
}
int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif // LOCAL
int T;
scanf("%d",&T);
//cout<<T<<endl;
while(T--)
{
Init();//if(T==6)printf("%d\n",flag);
if(flag==true)Solve();
if(flag)printf("Shoot!\n");
else printf("Poor Mays!\n");
//Solve();
}
return 0;
}
![CF1394C 计算几何[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)