A Wrestling Match

判断二分图，特判没属性的孤点。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1050;
vector<int> e[maxn];
int n,m,x,y;
int colour[maxn];
int du[maxn];
int vis[maxn];
bool dfs(int v,int c) {
    colour[v]=c;
    for(int i=0;i<(int)e[v].size();i++) {
        if(colour[e[v][i]]==c) {
            return false;
        }
        if(colour[e[v][i]]==0&&!dfs(e[v][i],-c))
            return false;
    }
    return true;
}
int main(){
    while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF){
        for(int i=0;i<=n;i++) e[i].clear();
        memset(du,0,sizeof du);
        while(m--){
            int u,v;
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
            du[u]++;du[v]++;
        }
        memset(colour,0,sizeof(colour));
        memset(vis,0,sizeof vis);
        bool ptd=0;
        for(int i=1;i<=x;i++){
            int x;
            scanf("%d",&x);
            colour[x]=1;
            vis[x]=1;
        }
        for(int i=1;i<=y;i++){
            int x;
            scanf("%d",&x);
            colour[x]=-1;
            if(vis[x]==1){
                ptd=1;
                break;
            }
            vis[x]=-1;
        }
        if(ptd){
            puts("NO");
            continue;
        }
        for(int i=1;i<=n;i++){
            if(vis[i]==0 && du[i]==0){
                puts("NO");
                ptd=1;
                break;
            }
        }
        if(ptd)continue;
        bool flag=true;
        for(int i=1;i<=n && flag;i++){
            if(colour[i]==1) flag=dfs(i,1);
            else if(colour[i]==-1) flag=dfs(i,-1);
        }
        for(int i=1;i<=n && flag;i++){
            if(colour[i]==0) flag=dfs(i,1);
        }
        // for(int i=1;i<=n;i++)
        //  printf("%d ",colour[i]);
        // puts("");
        for(int i=1;i<=n;i++){
            if(colour[i]==0){
                flag=false;
                break;
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

C Game of Taking Stones

威佐夫博弈
求$\frac{\sqrt(5)+1}{2}b$。

import java.util.*;
import java.math.*;

public class Main{
    
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        BigDecimal k = null;
        BigDecimal eps = BigDecimal.valueOf(0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001);
        BigDecimal l=BigDecimal.valueOf(1.0);
        BigDecimal r=BigDecimal.valueOf(3.0);
        BigDecimal Five=BigDecimal.valueOf(5.0);
        for(int i=1;i<=2000;i++){
            BigDecimal mid=l.add(r);
            mid=mid.divide(BigDecimal.valueOf(2.0));
            BigDecimal p = mid.multiply(mid);
            int pk = p.compareTo(Five);
            if(pk<=0){
                l=mid.add(eps);
                k=mid;
            } else {
                r=mid.subtract(eps);
            }
        }
        //System.out.println(k);
        k=k.add(BigDecimal.valueOf(1.0));
        k=k.divide(BigDecimal.valueOf(2.0));
        BigDecimal a,b;
        while(cin.hasNext()){
            a=cin.nextBigDecimal();b=cin.nextBigDecimal();
            int pk=a.compareTo(b);
            if(pk<0){
                BigDecimal tmp = a;
                a=b;
                b=tmp;
            }
            BigDecimal ans = a.subtract(b);
            ans=ans.multiply(k);
            ans=ans.subtract(b);
            pk = ans.compareTo(BigDecimal.valueOf(1.0));
            int pt=ans.compareTo(BigDecimal.valueOf(0.0));
            if(pk<0 && pt>=0) System.out.println(0);
            else System.out.println(1);
        }
    }
}

D A Simple Math Problem

设$G=gcd(a,b)$。
$gcd(a,b)=gcd(x+y,lcm(x,y))=gcd(x+y,ky)=gcd(x+y,y)=gcd(x,y)$
那么等式$\frac{x}{G}+\frac{y}{G}=\frac{a}{G}$。
$lcm(x,y)=\frac{xy}{gcd(x,y)}$,
$\frac{x}{G}\frac{y}{G}=\frac{b}{G}$.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll a, b, x, y;

ll getsqrt(ll a){
    if(a==0) return 0;
    ll l=1,r=1e9;
    while(l<=r){
        ll mid = (l+r)/2;
        ll p=mid*mid;
        if(p==a)
            return mid;
        if(p<a)
            l=mid+1;
        if(p>a)
            r=mid-1;
    }
    return -1;
}

int main() {
    //freopen("in.txt","r",stdin);
    while (~scanf("%lld%lld", &a, &b)) {
        ll G = gcd(a, b);
        ll aa = a / G;
        ll bb = b / G;
        ll d = aa * aa - 4ll * bb;
        if(d<0){
            puts("No Solution");
            continue;           
        }
        ll t = getsqrt(d);
        //cout<<t<<endl;
        if(t==-1){
            puts("No Solution");
            continue;
        }
        ll ans1=(aa-t)/2;
        ll ans2=(aa+t)/2;
        if(ans1*2ll!=aa-t){
            puts("No Solution");
            continue;
        }
        ans1*=G;
        ans2*=G;
        if(ans1>ans2) swap(ans1,ans2);
        if(ans1<=0 || ans2>a){
            puts("No Solution");
            continue;           
        }
        printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}

F Detachment

连续整数相乘时值很大。考虑到1没有贡献，那么必然是从2开始。
5=2+3
9=2+3+4
14=2+3+4+5
....
这些是分界。
多余的时候挂在末尾，都加1就行。
预处理fac和inv。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const int N = 1e5;
ll fac[maxn];
ll inv[maxn];
ll S[maxn];

inline ll power(ll a, ll n, ll p) {
    ll ret = 1; ll now = a;
    while (n != 0) {
        if (n & 1)
            ret = ret * now % p;
        now = now * now % p;
        n >>= 1;
    }
    return ret;
}

void init() {
    fac[0] = 1;
    for (ll i = 1; i <= N; i++)
        fac[i] = fac[i - 1] * i % mod;
    inv[N] = power(fac[N], mod - 2, mod);
    for (ll i = N; i >= 1; i--)
        inv[i - 1] = inv[i] * i % mod;
    S[2]=2;
    for(ll i=3;i<=N;i++)
        S[i]=S[i-1]+i;
}

int main() {
    init();
    int t;
    ll n;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &n);
        if (n <= 4) {
            printf("%lld\n", n);
            continue;
        }
        ll x;
        ll l = 2, r = N;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if ( S[mid] <= n) {
                l = mid + 1;
                x = mid;
            } else {
                r = mid - 1;
            }
        }
        x--;
        ll avg = n / x;
        ll ans = 1;
        if (x & 1) {
            ll k = x / 2;
            ll left = avg - k;
            ll right = avg + k;
            ll sum = (left + right) * x / 2;
            ll tmp = n - sum;
            while (tmp >= x) {
                tmp -= x;
                left++;
                right++;
            }
            if (tmp == 0) {
                ans = fac[right] * inv[left - 1] % mod;
            } else {
                ll lright = right - tmp;
                right++;
                ans = fac[lright] * inv[left - 1] % mod * fac[right] % mod * inv[lright + 1] % mod;
            }
        } else {
            ll k = x / 2;
            ll left = avg - k;
            ll right = avg + k - 1;
            ll sum = (left + right) * x / 2;
            ll tmp = n - sum;
            while (tmp >= x) {
                left++; right++;
                tmp -= x;
            }
            if (tmp == 0) {
                ans = fac[right] * inv[left - 1] % mod;
            } else {
                ll lright = right - tmp;
                right++;
                ans = fac[lright] * inv[left - 1] % mod * fac[right] % mod * inv[lright + 1] % mod;
            }
        }
        printf("%lld\n", ans % mod);
    }
    return 0;
}

H To begin or not to begin

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
    //freopen("in.txt","r",stdin);
    int n;
    while(~scanf("%d",&n))
        printf("%d\n",(n+1)%2);
    return 0;
}

I Convex

#include <bits/stdc++.h>

using namespace std;
const int maxn=20;
const  double pi=acos(-1);
int a[1111];
int main() {
    int n,d;
    while(scanf("%d%d",&n,&d)!=EOF) {
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
        }
        double ans = 0.0;
        for(int i=1;i<=n;i++) {
            ans+=0.5*d*d*sin(a[i]*pi/180.0);
        }
        printf("%.3lf\n",ans);
    }
    return 0;
}

J Find Small A

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
    //freopen("in.txt","r",stdin);
    int x,n;
    while(~scanf("%d",&n)){
        int cnt = 0;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            while(x){
                if(x % 256 == 97)
                    cnt++;
                x/=256;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

优质内容筛选与推荐>>
1、html5移动端meta自动适应标签
2、[yii]Trying to get property of non-object
3、vs 2010 遇到了异常，某个扩展库所致，Activitylog.xml
4、虚拟机是如何加载类的
5、lrzsz安装