第一次AtCoder体验
开场送温暖
1
2
3
4
5
6
|
int main()
{
int r;cin>>r;
cout<<r*r<<endl;
return 0;
}
|
直接判断前一半后一半是否相等即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
int main()
{
cin>>n>>s;
if(s.size()%2==1) puts("No");
else
{
for(int i=0;i<s.size()/2;i++)
{
if(s[i]!=s[i+(s.size()/2)])
{
puts("No");
return 0;
}
}
puts("Yes");
}
return 0;
}
|
emmm这题我现场浪费了好多时间 算错了分母结果1，2样例都很巧对了然后第三个样例数字很小让我一度以为哪里精度炸了...
我们可以这样考虑 对于两个点之间的路径计算这个路径的贡献 剩下$n-2$个点 有$(n-2)!$种路线 然后我们可以把这条路径插空插到这$n-2$条路里 所以一共有$(n-2)!(n-1)=(n-1)!$种情况都会有这条路径 那么总贡献就是$d\cdot (n-1)!$而一共有$n!$种路径 所以平均长度就是$\frac{d}{n}$
我们直接去枚举所有路径$(i,j)$然后计算贡献即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
ll n;
double x[15],y[15];
double calc(int a,int b)
{
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int main()
{
cin>>n;
double res=1.0;
double ans=0.0;
res=n;
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(j==i) continue;
ans+=calc(i,j)/res;
}
}
printf("%.10Lf\n",ans);
return 0;
}
|
一道还算是比较简单的数学题？
既然最后要从$(0,0)$到$(X,Y)$而且只有两种走法 那我们可以假设第一种走了$a$次 第二种走了$b$次 那么可得方程$a+2b=X,2a+b=Y$解得$a= \frac{2y-x}{3},b= \frac{2x-y}{3}$
那么剩下就是一个组合数学问题 总共走$a+b$次其中需要$a$次走第一种情况 那么答案就是$C_{a+b}^{a}\mod p$然后就是比较套路的组合数计算 可以$O(n)$处理乘阶和逆元 不过我就随便写了个快速幂反正题目要求不高
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
const int p=1e9+7;
ll x,y;
ll calc(ll n)
{
ll res=1;
for(ll i=1;i<=n;i++) res=res*i%p;
return res%p;
}
ll ksm(ll a,ll b)
{
ll res=1%p;
while(b)
{
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
int main()
{
cin>>x>>y;
if(2*x-y<0||(2*x-y)%3!=0) puts("0");
else if(2*y-x<0||(2*y-x)%3!=0) puts("0");
else
{
ll a=(2*y-x)/3;
ll b=(2*x-y)/3;
ll temp=(x+y)/3;
temp=calc(temp);
a=calc(a),b=calc(b);
ll ans=temp%p*ksm(a,p-2)%p*ksm(b,p-2)%p;
cout<<ans%p<<endl;
}
return 0;
}
|
这题感觉还是挺有趣的 让我想起在hdoj上做的一题 我大概看了眼题解感觉好像做法不太一样 我是一种贪心的思想
首先这道题肯定需要跑一个01背包 但是它也只能跑一个01背包 数据范围不允许我们去做一些枚举的操作 所以自然想到贪心 因为到了$T$以后就不能再吃了而之前吃的还可以继续 我们可以想到在$T-1$处做点什么
那应该把什么东西放进去呢 其实这里我卡了蛮久的还WA了一发放之前体积最大的进去 不太行 放价值最大的也不太行 其实关键在于我们需要放一个最合适的进去
所以我们可以跑完01背包以后把具体情况跑出来（背包体积是$T-1$） 之后对于没有选到的我们按价值排序 选一个最大的放进去即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
const int maxn=3050;
int n,m;
int v[maxn],w[maxn],f[maxn][maxn];
int p[maxn],num;
int main()
{
cin>>n>>m;
int maxx=0,pos=0;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m-1;j++)
{
f[i][j]=f[i-1][j];
if(j-v[i]>=0) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
int temp=m-1;
for(int i=n;i>=1;i--)
{
if(temp-v[i]>=0&&f[i][temp]==f[i-1][temp-v[i]]+w[i])
{
temp-=v[i];
}
else p[++num]=w[i];
}
sort(p+1,p+num+1);
cout<<f[n][m-1]+p[num]<<endl;
return 0;
}
|
待补 比赛时候没高兴看