Codeforces每日一练 1030D+1154E+540D

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}$就是一对符合的因子

#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
"<<"0 "<<2*m/k;}
        else {cout<<2*n/tmp<<" 0
"<<"0 "<<m*tmp/k;}
    }
    return 0;
}

1154E Two Teams

传送门
镜像
1800 数据结构
题意：从两个教练依次选人，每次选未被选择的学生中能力最大的，并从其两侧各选连续的k个人，输出最后每个人所在队伍的编号。
这道题方法就很多了，可以线段树，链表，或者用set模拟。
这里简单说说双向链表的做法，每次找到当前最大值，沿着两边的方向各找k个，处理编号后删去，将剩下的两段连接即可。

#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个布，捕食关系就是剪刀石头布的关系，每次选两个，如果不同就按照捕食关系删去被捕食的一个，询问足够长的时间后，仅剩石头/剪刀/布的概率
开个三维数组记录石头、剪刀、布的数量，然后就是转移方程

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);

从左到右分别是石头、剪刀、布的数量。
需要注意的一点是，取生物时，只需要利用不同的情况计算概率即可，为什么不考虑相同呢？如果取到相同的生物，相当于当前的状态没有发生变化，那么就会一直保持当前的状态直到取到两个不同的生物，所以取相同的生物的情况不需要加入我们考虑的范围内。

#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;
}