头部背景图片
Decaku 's Blog |
Decaku 's Blog |

2018牛客国庆集训派对 day3

D:

签到。


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
#include<bits/stdc++.h>
using namespace std;
int n,m;
double a[1050];
int b[1050];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
int cnt=0;
for(int i=0; i<n; i++)
{
cin>>a[i]>>b[i];
if(b[i])
cnt++;
}
sort(a,a+n,cmp);
double ans=0;
cnt=min(cnt,m);
for(int i=0;i<cnt;i++)
{
ans+=a[i]/2;
}
for(int i=cnt;i<n;i++)
ans+=a[i];
printf("%.1f\n",ans);
}
}

H:

发现和树的结构没有关系,只要考虑如何把树上的结点分成几部分,推完发现是个组合数取模,预处理阶乘,用乘法逆元即可。


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
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int mod=1e9+7;
ll fac[maxn];
void init_fac()
{
fac[0]=fac[1]=1;
for(int i=2;i<maxn;i++)
fac[i]=i*fac[i-1]%mod;
}

ll quickpow(ll a,ll n)
{
ll ret=1;
while(n)
{
if(n&1) ret=ret*a%mod;
a=a*a%mod;
n>>=1;
}
return ret;
}
ll C(ll a,ll b)
{
return fac[a]*quickpow(fac[b],mod-2)%mod*quickpow(fac[a-b],mod-2)%mod;
}

int main()
{
int t;
scanf("%d",&t);
init_fac();
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
}
ll ans=C(n-1,m-1)*fac[m]%mod;
printf("%lld\n",ans);
}
}

A:

马走日问题,因为棋盘太大,可以大范围贪心+小范围暴搜。题解是找规律。


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
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

int main()
{
int x, y, ans;
int t;
cin>>t;
while(t--)
{
cin>>x>>y;
x=abs(x);
y=abs(y);
if(x>y)swap(x, y);

if(y==x*2)
{
printf("%d\n", (x+y)/3);
continue;
}
if(y<=2*x)
{
if(x==1&&y==1)
ans = 2;
else if(x==2&&y==2)
ans = 4;
else
ans = (x+y)/3+(x+y)%3;
}
else
{
ans=x;
int c=(y-2*x)%4;
ans+=c;
ans+=(y-2*x-c)/2;
if(y==1&&x==0)
ans=3;
}
printf("%d\n",ans);
}
return 0;
}
avatar Decaku 很菜但也很想carry