13届河南省省赛

13届河南省省赛I题（dfs）

# include<iostream>
# include<algorithm>
# include<string>
# include<cstring>

using namespace std;

int a[10];
int g[10];

int to1(int i)
{
    return (i+2)%8+1;
}

int to2(int i)
{
    return (i+4)%8+1;
}

bool dfs(int x, int num)
{
    g[x] = 1;
    if(num==8)
    {
        return true;
    }
    
    for(int i=1; i<=8; ++i)
    {
        if(!g[i])
        {
            if(g[to1(i)])   return false;
            else   return dfs(g[to1(i)], num+1);
            
            if(g[to2(i)])   return false;
            else   return dfs(g[to2(i)], num+1);
        }
    }
}

int main()
{
    int t;
    cin>>t;
    
    while(t--)
    {
        int num = 0;
        bool cha = false;
        string s;
        cin>>s;
        for(int i=0; i<8; ++i)
            if(s[i]=='1')
            {
                num++;
                a[i+1] = 1;
            }
            else   a[i+1] = 0;
        
        if(num==8)
        {
            cout<<"Yes"<<endl;
            continue;
        }
        
        for(int i=1; i<=8; ++i)
        {
            memcpy(g, a, sizeof a);
            
            if(!g[i])
            {
                if(g[to1(i)])   continue;
                else
                {
                    if(dfs(g[to1(i)], num+1))
                        cha = true;
                }
                
                if(g[to2(i)])   continue;
                else
                {
                    if(dfs(g[to2(i)], num+1))
                        cha = true;
                }
                
                if(cha)   break;
            }
        }
    
        if(cha)   cout<<"Yes"<<endl;
        else   cout<<"No"<<endl;
    }
    
    return 0;
}

//L题
# include<iostream>
# include<algorithm>

using namespace std;

bool ck(double a, double b, double x, double y)
{
    if(b*b*x*x + a*a*y*y <= a*a*b*b)   return true;
    else   return false;
}

int main()
{
    int t;
    cin>>t;
    
    while(t--)
    {
        double cnt = 0, num = 0;
        double a1, b1, a2, b2;
        cin>>a1>>b1>>a2>>b2;
        
        for(double i=-8; i<=8; i+=0.005)
            for(double j=-8; j<=8; j+=0.005)
            {
                if(ck(a1, b1, i, j) || ck(a2, b2, i, j))   cnt++;
                num++;
            }
        
        double ans = cnt*1.0/40000*1.0;
        
        printf("%.1f\n", ans);
    }
    
    return 0;
}

J题：甜甜圈

# include<iostream>
# include<algorithm>
# include<cmath>

using namespace std;

const int N = 1e5+10;

struct Range
{
    int val, num;
    bool operator< (const Range &w)const
    {
        return val > w.val;
    }
}range[N];

int n, m;
int a1[N], a2[N], b[N];
int tr[N];

int lowbit(int x)
{
    return x & -x;
}

void modify(int x, int v)
{
    for(int i=x; i<=N; i+=lowbit(i))   tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for(int i=x; i; i-=lowbit(i))   res += tr[i];
    return res;
}

int main()
{
    cin>>n>>m;
    for(int i=1; i<=n+m; ++i)   modify(i, 1);
    for(int i=1; i<=n; ++i)   cin>>a1[i];
    for(int i=1; i<=m; ++i)
    {
        cin>>a2[i];
        range[i] = {a2[i], i};
    }
    
    for(int i=n, j=m+1; i; --i, ++j)
        range[j] = {a1[i], j};
    
    sort(range+1, range+n+m+1);
    
    int l, r;
    int xx = range[1].num;
    if(xx>m)   r = m;
    else   r = m+1;
    
    int ans = 0;
    for(int i=1; i<=n+m; ++i)
    {
        int x = range[i].num;
        l = r, r = x;
        
        // cout<<l<<' '<<r<<endl;
        
        modify(r, -1);
        int res = abs(query(r)-query(l));
        // cout<<res<<endl;
        ans += res;
        
    }
    // cout<<endl;
    cout<<ans<<endl;
    
    return 0;
}