1030D Vasya and Triangle
传送门
1700 数论+几何
题意：给定整数n,m,k，是否能在x∈[0,n],y∈[0,m]的范围内找出三个整数点使得构成的三角形面积为$\frac{nm}{k}$。
不难看出构成的三角形面积必定为整数，那么当且仅当$\frac{2nm}{k}$为整数的时候可以找到三个符合条件的格点，那么现在只需要将$\frac{2nm}{k}$分解为一个小于等于n和一个小于等于m的因子即可。考虑求出a=gcd(n,k)，如果a为1，那么n和$\frac{2m}{k}$就是一对满足的因子，如果不为1，那么$\frac{2n}{a}$和$\frac{am}{k}$就是一对符合的因子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 5005
#define ll long long
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
int main()
{
IOS
ll n,m,k;
cin>>n>>m>>k;
if((n*m*2)%k!=0)cout<<"NO";
else{
cout<<"YES"<<endl;
cout<<"0 0"<<endl;
ll tmp=gcd(2*n,k);
if(tmp==1){cout<<n<<" 0\n"<<"0 "<<2*m/k;}
else {cout<<2*n/tmp<<" 0\n"<<"0 "<<m*tmp/k;}
}
return 0;
}
|
1154E Two Teams
传送门
1800 数据结构
题意：从两个教练依次选人，每次选未被选择的学生中能力最大的，并从其两侧各选连续的k个人，输出最后每个人所在队伍的编号。
这道题方法就很多了，可以线段树，链表，或者用set模拟。
这里简单说说双向链表的做法，每次找到当前最大值，沿着两边的方向各找k个，处理编号后删去，将剩下的两段连接即可。
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;
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define maxn 200005
int n,k;
int a[maxn],nxt[maxn],pre[maxn],sig[maxn];
map<int,int> mp;
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){cin>>a[i];nxt[i]=i+1;mp[a[i]]=i;pre[i]=i-1;}
int cnt=0;
pre[0]=0;
nxt[0]=1;
pre[n+1]=n;
nxt[n+1]=n+1;
for (int j = n; j >=1 ; --j) {
if(mp[j]!=0){
int l=mp[j],r=mp[j];
sig[mp[j]]=cnt;
mp[j]=0;
for (int i = 0; i <k ; ++i) {
l=pre[l];
if(l==0)break;
sig[l]=cnt;
mp[a[l]]=0;
}
for (int m = 0; m <k ; ++m) {
r=nxt[r];
if(r==n+1)break;
sig[r]=cnt;
mp[a[r]]=0;
}
nxt[pre[l]]=nxt[r];
pre[nxt[r]]=pre[l];
cnt++;
cnt%=2;
}
}
for (int i = 1; i <=n ; ++i) {
cout<<sig[i]+1;
}
return 0;
}
|
540D Bad Luck Island
传送门
2100 概率dp
题意：一座岛上有三种生物，r个石头，s个剪刀，p个布，捕食关系就是剪刀石头布的关系，每次选两个，如果不同就按照捕食关系删去被捕食的一个，询问足够长的时间后，仅剩石头/剪刀/布的概率
开个三维数组记录石头、剪刀、布的数量，然后就是转移方程
1
2
3
| dp[i][j-1][k]+=dp[i][j][k]*x*y/(x*y+y*z+z*x);
dp[i-1][j][k]+=dp[i][j][k]*x*z/(x*y+y*z+z*x)
dp[i][j][k-1]+=dp[i][j][k]*y*z/(x*y+y*z+z*x);
|
从左到右分别是石头、剪刀、布的数量。
需要注意的一点是，取生物时，只需要利用不同的情况计算概率即可，为什么不考虑相同呢？如果取到相同的生物，相当于当前的状态没有发生变化，那么就会一直保持当前的状态直到取到两个不同的生物，所以取相同的生物的情况不需要加入我们考虑的范围内。
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
| #include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 105
#define ll long long
#define ld long double
int r,s,p;
ld dp[maxn][maxn][maxn];
ld a=0,b=0,c=0;
#define eps 1e-10
int main()
{
cin>>r>>s>>p;
dp[r][s][p]=1.0;
for (int i = r; i >=0 ; --i) {
for (int j = s; j >=0 ; --j) {
for (int k = p; k >=0 ; --k) {
ld x=i,y=j,z=k;
if(x*y+y*z+z*x<=eps)continue;
if(j>=1){
dp[i][j-1][k]+=dp[i][j][k]*x*y/(x*y+y*z+z*x);
}
if(i>=1){
dp[i-1][j][k]+=dp[i][j][k]*x*z/(x*y+y*z+z*x);
}
if(k>=1){
dp[i][j][k-1]+=dp[i][j][k]*y*z/(x*y+y*z+z*x);
}
}
}
}
for (int i = r; i >0 ; --i) a+=dp[i][0][0];
for (int i = s; i >0 ; --i) b+=dp[0][i][0];
for (int i = p; i >0 ; --i) c+=dp[0][0][i];
printf("%.12Lf %.12Lf %.12Lf",a,b,c);
return 0;
}
|