2016 Multi-University Training Contest 2(部分) - dblank

2016 Multi-University Training Contest 2(部分)

<h2>1001 Acperience</h2>
思路:这个算是简单的,直接把所有的等式展开,最后是一个这样的等式(w1w1 + w2w2 + ·····+wnwn) - 2a(w1b1 + w2b2+······wnbn) + na*a.

我们可以看出与后面两项有关,然后求导找到最大值,即(w1b1+w2b2+······+wnbn)最大,w全部abs即最大。直接算就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e6 + 10, Mod = 100000007;
typedef long long ll;
int w[N];
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a%b);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        scanf("%lld", &n);
        ll sum = 0, x = 0;
        for(int i = 1; i<=n; i++)
        {
            scanf("%d", &w[i]);
            if(w[i]<0)
                w[i] = -w[i];
            sum += 1LLw[i]w[i];
            x += w[i];
        }
        x*=x;
        if(x/n == sum)
            printf("0/1n");
        else
        {
            ll G = gcd(x, 1LL*n);
            x/=G;
            n/=G;
            printf("%lld/%lldn", sum*n-x, n);
        }
    }
    return 0;
}

<h2>1005  Eureka</h2>
思路:通过它的集合的条件会发现,只有共线的点集才是符合的,这样的话,我们找到每一条直线上的点,通过组合数求解算出答案。

要找到有多少每一条直线的共线的点,我们可以先按照x,y双关键字排序,然后枚举起点,用这个起点作为集合的起点,因为可以有共点的集合也是合法的集合,我们可以先把共点统计出来,然后一定存在这个端点的共点集合的种类就2^cnt - 1,然后就是不共点共线的集合,把所有以该端点的直线向量求出,并且进行gcd后排序,二胺后我们就可以求出共线的点有多少个,同样考虑共点集的影响,所以这个集合的个数就是2^cnt * (2^num -1)个。

#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<iostream>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e3 + 10, Mod = 1000000007;
typedef long long ll;
using namespace std;
struct Point
{
    int x, y;
    Point() {}
    Point(int _x, int _y): x(_x), y(_y) {}
    Point operator - (const Point &rhs) const
    {
        return Point(x - rhs.x, y - rhs.y);
    }
    bool operator < (const Point &rhs) const
    {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
    bool operator == (const Point &rhs) const
    {
        return x == rhs.x && y == rhs.y;
    }
    void GCD()
    {
        int g = std::__gcd(abs(x), abs(y));
        if (g) x /= g, y /= g;
    }
};
int main()
{
    Point p[N], q[N];
    int bit[N];
    bit[0] = 1;
    for(int i = 1; i<=1000; i++)
    {
        bit[i] = bit[i-1]*2%Mod;
    }
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 0; i<n; i++)
        {
            scanf("%d%d", &p[i].x, &p[i].y);
        }
        sort(p, p+n);
        int ans = 0;
        for(int i = 0; i<n; i++)
        {
            int cnt = 0, k = 0;
            for(int j = i + 1; j<n; j++)
            {
                if(p[j] == p[i])
                    cnt++;
                else
                    q[k++] = p[j] - p[i];
            }
            for(int j = 0; j<k; j++) q[j].GCD();
            ans = (ans + bit[cnt] - 1)%Mod;
            sort(q, q+k);
            for (int x = 0, y; x < k; x = y)
            {
                for (y = x; y < k && q[x] == q[y]; ++y);
                ans = (ans + 1LLbit[cnt](bit[y-x]-1))%Mod;
            }
        }
        printf("%dn", ans);
    }
    return 0;
}

<h2>1009 It's All In The Mind</h2>
思路:很明显是,max(a1+a2) 和min(sum(a1+······an))得到的数最大,然后a是0~100,单调不递增的。直接i大于3的等于后缀最小值,i小3的前缀等于最大值就好。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 100000007;
typedef long long ll;
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a%b);
}
int a[N], mx[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        memset(a, -1, sizeof(a));
        int x, y;
        for(int i = 1; i<=m; i++)
        {
            scanf("%d%d", &x, &y);
            a[x] = y;
        }
        mx[n+1] = 0;
        for(int i = n; i>=1;i--)
        {
            mx[i] = max(mx[i+1],a[i]);
        }
        int maxx;
        for(int i = 1; i<=n; i++)
        {
            if(i==1)
            {
                if(a[i] == -1)
                    a[i] = 100;
                maxx = a[i];
            }
            else
            {
                if(a[i]==-1 && i>=3)
                  a[i] = mx[i+1], maxx = min(maxx,a[i]);
                else if(a[i] == -1 && i <3)
                    a[i] = maxx;
                else
                    maxx = min(a[i], maxx);
            }
        }
        int sum = 0;
        x=  0;
        for(int i = 1; i<=min(2, n); i++)
            x+= a[i];
        for(int i = 1; i<=n; i++)
            sum+=a[i];
            int G = gcd(sum, x);
        printf("%d/%dn", x/G, sum/G);
    }
    return 0;
}

<h2>1011 Keep On Movin</h2>
思路:直接统计为奇数的个数并,然后剩下的全部对半分,最后统计一下就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 100000007;
typedef long long ll;
int a[N];
int main()
{
    int n, t;
    cin>>t;
    while(t--)
    {
        scanf("%d", &n);
        ll sum  = 0;
        for(int i = 1; i<=n; i++)
            scanf("%d", &a[i]);
        int ans = 0;
        for(int i  = 1; i<=n; i++)
            {
                if(a[i] & 1)
                {
                    sum += (a[i] - 1)/2;
                    ans ++;
                }
                else
                {
                    sum += a[i]/2;
                }
            }
        if(ans == 0)
            cout<<sum * 2<<endl;
        else if(sum % ans == 0)
            cout<<sum/ans*2 + 1<<endl;
        else
            cout<<sum/ans * 2 + 1<<endl;
    }
    return 0;
}

<h2>1012 La Vie en rose</h2>
思路:直接暴力

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 100000007;
typedef long long ll;
int Next[N], n, m;
char s[N*10], x[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d%d", &n, &m);
        scanf("%s", s);
        scanf("%s", x);
        for(int i = 0;i<n; i++)
        {
            int ok = 1;
            for(int j = 0; j<m; j++)
            {
                if(x[j] != s[i+j])
                {
                    if(x[j+1] == s[j+i] && x[j] == s[i+j+1])
                        j++;
                    else
                    {
                        ok = 0;
                        break;
                    }
                }
            }
            if(ok) printf("1");
            else printf("0");
        }
        printf("n");
    }
    return 0;
}

 

相关文章

发表新评论