首页 > 程序开发 > 软件开发 > 其他 >

2014ACM/ICPC亚洲区鞍山赛区现场赛 题解

2016-11-02

对于每一个窗口,有两个属性:优先级+说过的单词数,支持8个操作:新建窗口,关闭窗口并输出信息,聊天(置顶窗口加单词),把优先级最高的窗口移到最前,把当前第i个窗口移到最前,把选择的窗口移到最前,把某个窗口置顶,把置顶窗口取消置顶。

【B】题意:对于每一个窗口,有两个属性:优先级+说过的单词数,支持8个操作:新建窗口,关闭窗口并输出信息,聊天(置顶窗口加单词),把优先级最高的窗口移到最前,把当前第i个窗口移到最前,把选择的窗口移到最前,把某个窗口置顶,把置顶窗口取消置顶。最后按优先级输出每个窗口的优先级以及单词数。【解题方法】没啥说的,就是模拟,注意初始化,被坑了一万年。

【代码】

//  
//Created by just_sort 2016/10/28  
//Copyright (c) 2016 just_sort.All Rights Reserved  
//  
  
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>  
#include <ext/pb_ds/hash_policy.hpp>  
#include <set>  
#include <map>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
using namespace std;  
using namespace __gnu_pbds;  
typedef long long LL;  
typedef pair<int, LL> pp;  
#define MP(x,y) make_pair(x,y)  
const int maxn = 200005;  
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;  
//head  
  
vector <pp> p;  
int find(int x){  
    for(int i = 0; i < p.size(); i++){  
        if(p[i].first == x){  
            return i;  
        }  
    }  
    return -1;  
}  
  
void erase(int x){  
    int i = 0;  
    for(auto it = p.begin(); it != p.end(); it++, i++)  
    if(i == x){  
        p.erase(it);  
        return ;  
    }  
}  
  
int x;  
int now;  
//1  
void Add()  
{  
    scanf("%d",&x);  
    if(find(x) != -1) printf("same priority.\n");  
    else{  
        p.push_back(MP(x, 0));  
        printf("success.\n");  
    }  
}  
//2  
void Close()  
{  
    scanf("%d",&x);  
    int t = find(x);  
    if(t == -1) printf("invalid priority.\n");  
    else{  
        if(x == now) now = 0;  
        printf("close %d with %I64d.\n",p[t].first,p[t].second);  
        erase(t);  
    }  
}  
//3  
void Chat()  
{  
    scanf("%d",&x);  
    if(p.size() == 0) printf("empty.\n");  
    else{  
        if(now) p[find(now)].second += 1LL*x;  
        else p[0].second += 1LL*x;  
        printf("success.\n");  
    }  
}  
//4  
void Rotate(int x)  
{  
    //scanf("%d",&x);  
    if(x < 1 || x > p.size())  
        printf("out of range.\n");  
    else{  
        pp aa = p[x - 1];  
        erase(x - 1);  
        p.insert(p.begin(),aa);  
        printf("success.\n");  
    }  
}  
//5  
void Prior()  
{  
    if(p.size() == 0)  
    {  
        printf("empty.\n");  
    }  
    else  
    {  
        int mxv = 0, mxp = -1;  
        for(int i = 0; i < p.size(); i++)  
        {  
            if(p[i].first > mxv)  
            {  
                mxv = p[i].first;  
                mxp = i;  
            }  
        }  
        Rotate(mxp+1);  
    }  
}  
//6  
void Choose()  
{  
    scanf("%d",&x);  
    int pos = find(x);  
    if(pos == -1)  
        printf("invalid priority.\n");  
    else{  
        Rotate(pos+1);  
    }  
}  
//7  
void Top()  
{  
    scanf("%d",&x);  
    if(find(x) == -1) printf("invalid priority.\n");  
    else{  
        now = x;  
        printf("success.\n");  
    }  
}  
//8  
void Untop()  
{  
    if(now){  
        now = 0;  
        printf("success.\n");  
    }  
    else{  
        printf("no such person.\n");  
    }  
}  
  
int main()  
{  
    int T,ks = 1;  
    scanf("%d",&T);  
    while(T--)  
    {  
        int n;  
        scanf("%d",&n);  
        now = 0;  
        p.clear();  
        char op[20];  
        for(int i = 1; i <= n; i++)  
        {  
            scanf("%s",op);  
            printf("Operation #%d: ", i);  
            if(strcmp(op,"Add") == 0) Add();  
            else if(strcmp(op,"Close") == 0) Close();  
            else if(strcmp(op,"Chat") == 0) Chat();  
            else if(strcmp(op,"Rotate") == 0){  
                scanf("%d",&x);  
                Rotate(x);  
            }  
            else if(strcmp(op,"Prior") == 0) Prior();  
            else if(strcmp(op,"Choose") == 0) Choose();  
            else if(strcmp(op,"Top") == 0) Top();  
            else if(strcmp(op,"Untop") == 0) Untop();  
        }  
        //cout<<now<<endl;  
        //cout<<p.size()<<endl;  
        if(now)  
        {  
            x = find(now);  
            if(p[x].second != 0) printf("Bye %d: %I64d\n", p[x].first, p[x].second);  
            erase(x);  
        }  
        for(int i = 0; i < p.size(); i++)  
        {  
            if(p[i].second)  
            {  
                printf("Bye %d: %I64d\n", p[i].first, p[i].second);  
            }  
        }  
    }  
    return 0;  
}

【C】题意:给了n个数,求满足gcd(a,b)=1&&gcd(a,c)=1&&gcd(b,c)=1或者gcd(a,b)!=1&&gcd(a,c)!=1&&gcd(b,c)!=1的三元组的组数?

如果三个数a, b, c不符合条件,那么一定有一对是互质的,有一对是不互质的。不妨令a, b互质,b, c不互质。于是我们可以枚举b来统计答案。在除了b自己的所有数中,要么与b互质,要么与b不互质。假设n个数中有x个与b不互质的数,那么b对答案的贡献就是(x - 1) * (n - x)。那么问题来了,怎么求得n中有多少个数与b不互质呢?我们发现2 * 3 * 5 * 7 * 11 * 13 * 17 > 100000,也就是说每个数最多只有6个不同的因子,那么就可以用容斥原理求出多少个与b不互质的数。要使用容斥原理的话,我们还要知道对于每一个z,n个数中有多少个数是z的倍数,这个可以用筛法nlogn地求出来。于是我们就可以O(nn&minus;&minus;&radic;+nlogn+64n)

地求出答案。注意这里的求出答案之后要除以2,这是因为如果a, c互质,那么可以交换b, c的位置;如果a, c不互质,那么可以交换a, b的位置,每个答案都被计算了两遍。

其实可以用筛法预处理把因式分解的 O(nn&minus;&minus;&radic;)

换成 O(nlogn) 。

【代码】

//  
//Created by just_sort 2016/10/27  
//Copyright (c) 2016 just_sort.All Rights Reserved  
//  
  
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>  
#include <ext/pb_ds/hash_policy.hpp>  
#include <set>  
#include <map>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
using namespace std;  
using namespace __gnu_pbds;  
#define MP(x,y) make_pair(x,y)  
typedef long long LL;  
const int maxn = 200005;  
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;  
//head  
  
int a[maxn], cnt[maxn];  
  
int main()  
{  
    int T, n;  
    scanf("%d",&T);  
    while(T--)  
    {  
        vector <int> tmp;  
        scanf("%d", &n);  
        memset(a, 0, sizeof(a));  
        memset(cnt, 0, sizeof(cnt));  
        LL ans = 0;  
        for(int i = 0; i < n; i++)  
        {  
            int x;  
            scanf("%d", &x);  
            a[x]++;  
        }  
        for(int i = 1; i < maxn; i++)  
        {  
            for(int j = i; j < maxn; j += i)  
            {  
                cnt[i] += a[j];  
            }  
        }  
        for(int i = 1; i < maxn; i++)  
        {  
            if(a[i])  
            {  
                tmp.clear();  
                int t = i;  
                int u = (int)sqrt(i);  
                for(int j = 2; j <= u && t > 1; j++)  
                {  
                    if(t%j == 0)  
                    {  
                        tmp.push_back(j);  
                        while(t%j == 0) t /= j;  
                    }  
                }  
                if(t > 1) tmp.push_back(t);  
                if(tmp.size() == 0) continue;  
                int sum = 0;  
                int v = tmp.size();  
                int nn = 1 << v;  
                for(int j = 1; j < nn; j++)  
                {  
                    int flag = 0;  
                    int mul = 1;  
                    for(int k = 0; k < v; k++)  
                    {  
                        if((j >> k) & 1){  
                            flag++;  
                            mul *= tmp[k];  
                        }  
                    }  
                    if(flag&1) sum += cnt[mul];  
                    else sum -= cnt[mul];  
                }  
                ans += (LL)max(0, sum-1) * (n - sum);  
            }  
        }  
        printf("%I64d\n", (LL)n * (n-1) * (n-2) / 6 - ans / 2);  
    }  
}

【D 表达式化简,想法题】题意:在一条直线上有n颗星星,一开始这n颗星星绕着重心转,现在我们可以把其中的任意k颗星星移动到这条直线上的任意位置然后围绕这个新的重心转, 这个星系的惯性值I = w1 * d1^2 + w2 * d2 ^ 2 +......+wn * dn ^ 2,其中wi表示第i颗星星的重量,di表示第i颗星星到这个星系的重心的距离.然后现在要你求转移k颗星星之后惯性值最小是多少?

【解题方法】n颗星星转移k颗后还剩下n-k颗是不能移动的,很显然转移的k颗星星一定是转移到重心的位置,然后每颗星星的重量都是1,所以求I时就可以不用管wi了,然后我们可以枚举n-k个星星所在的区间,而且可以确定这n-1个星星在位置上一定是连续的.然后枚举出了k个区间,怎么能在O(1)时间算出每个区间的I值呢?作如下转化(其中e表示重心的坐标):

 (x1-e)^2 + (x2-e)^2 (x3-e)^2+....(xn-e)^2
=x1^2 + x2^2+...xn^2 + n * e^2 - 2*e*(x1+x2+x3+...xn)

这样通过预先求出x1的平方到xn的平方的和还有x1到xn的和就可以在O(1)时间内求出I的值了.

【代码】

//  
//Created by just_sort 2016/10/27  
//Copyright (c) 2016 just_sort.All Rights Reserved  
//  
  
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>  
#include <ext/pb_ds/hash_policy.hpp>  
#include <set>  
#include <map>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
using namespace std;  
using namespace __gnu_pbds;  
#define MP(x,y) make_pair(x,y)  
typedef long long LL;  
const int maxn = 200005;  
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;  
  
int T, n, k;  
double pos[maxn], sum1[maxn], sum2[maxn];  
  
int main()  
{  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%d%d", &n,&k);  
        for(int i = 1; i <= n; i++) scanf("%lf", &pos[i]);  
        sort(pos+1, pos+n+1);  
        sum1[0] = sum2[0] = 0;  
        for(int i = 1; i <= n; i++){  
            sum1[i] = sum1[i-1] + pos[i];  
            sum2[i] = sum2[i-1] + pos[i] * pos[i];  
        }  
        int m = n - k;  
        if(m <= 1){  
            printf("0.000000000000\n");  
            continue;  
        }  
        double ans = sum2[m] + m * (sum1[m] / m) * (sum1[m] / m) - 2 * (sum1[m] / m) * sum1[m];  
        for(int en = m; en <= n; en++){  
            int st = en - m + 1;  
            double zhong = (sum1[en] - sum1[st-1]) / m;  
            double curans = sum2[en] - sum2[st-1] + m * zhong * zhong - 2.0 * zhong * (sum1[en] - sum1[st-1]);  
            ans = min(ans, curans);  
        }  
        printf("%.10f\n", ans);  
    }  
}

【E 暴力DP】题意:给一个m*m的矩阵,有n个数a[i]。然后定义score(i,j)是矩阵第i行第j列的值,i,j分别是a[i]和a[i+1]。现在给出了n个数a[i],如果a[i]是-1,那么就可以把a[i]变成1~n里面的任意一个数。现在问能得到的最大分数是多少。

【解题方法】设dp[i][j]代表前i个数最后一个为j时候的最大分数。

所以可以分情况讨论:

如果a[i]和a[i-1]都未知,那么dp[i][j]=max(dp[i][j],dp[i-1][k]+ms[k][j]);

如果a[i]未知,a[i-1]已知,那么dp[i][j]=max(dp[i][j],dp[i-1][a[i-1]]+ms[a[i-1]][j]);

如果a[i]已知,a[i-1]未知,那么dp[i][a[i]]=max(dp[i][a[i],dp[i-1][k]+ms[k][a[i]]);

【代码略】

【I 模拟 注意 int转成double 会丢失精度】

//  
//Created by just_sort 2016/10/24  
//Copyright (c) 2016 just_sort.All Rights Reserved  
//  
  
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>  
#include <ext/pb_ds/hash_policy.hpp>  
#include <set>  
#include <map>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
using namespace std;  
using namespace __gnu_pbds;  
typedef long long LL;  
const int maxn = 300005;  
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;  
//head  
  
double t[maxn], x[maxn], y[maxn];  
  
int main()  
{  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        int n;  
        scanf("%d",&n);  
        for(int i = 0; i < n; i++){  
            scanf("%lf%lf%lf",&t[i],&x[i],&y[i]);  
        }  
        double ans = 0;  
        for(int i = 1; i < n; i++){  
            double dis = sqrt((y[i]-y[i-1])*(y[i]-y[i-1])+(x[i]-x[i-1])*(x[i]-x[i-1]));  
            ans = max(dis/(t[i]-t[i-1]), ans);  
        }  
        printf("%.10f\n",ans);  
    }  
}
相关文章
最新文章
热点推荐