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

2016-11-02

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

【代码】

```//
//Created by just_sort 2016/10/28
//

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

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
{
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);
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的三元组的组数？

【代码】

```//
//Created by just_sort 2016/10/27
//

#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 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)```

【代码】

```//
//Created by just_sort 2016/10/27
//

#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时候的最大分数。

【代码略】

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

```//
//Created by just_sort 2016/10/24
//

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

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