2018年6月

[编程|1500分] 神奇盘子

时间限制:C/C++ 1秒,其他语言 2秒
空间限制:C/C++ 262144K,其他语言 524288K
Special Judge,64bit IO Format: %lld

题目描述

有一个神奇的盘子,形状为圆形。盘子上面爬着一个大象(视作一个点)。由于现实的扭曲,当大象在盘子某个直径的一端的时候,可以瞬间传送至直径的另一端。现在大象想去盘子上另外一点,问他最少需要移动多少距离。传送不计距离。

输入描述:

第一行一个整数r(1 <= r <= 1000)代表盘子的半径。
接下来两行两个整点分别代表大象所在的位置和大象目标的位置坐标。保证两个点都在圆内(可能在边界上),圆心在点(0, 0)上。

输出描述:

输出一个实数,代表大象最短需要移动多少距离。和标程相对或绝对相差1e-6都算正确。

示例1

输入

1
0 1
0 -1

输出

0.000000000000

示例2

输入

4
3 0
-3 0

输出

2.000000000000

说明

301312_1529636221266_A0DE9FC5C63D12A31918C9EE11768FDD.png

示例3

输入

100
-59 76
3 69

输出

62.393909959226

题解

中档题。个人认为是先取出一个大概的区间然后二分查找出答案的但是这样写太麻烦了于是……暴力出奇迹!直接分成足够多份暴力枚举即可。

#include<iostream>
#include<bitset>
#include<string>
#include<string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <stdio.h>
#include <set>
#include <queue>
#include <stack>
using namespace std;
const double n = 1000000;
const double pi=3.141592653589793238; 
double ans;
double r, xd1, yd1, xd2, yd2;
double pf(double a) {
    return a * a;
}
int main() {
    cin >> r;
    cin >> xd1 >> yd1;
    cin >> xd2 >> yd2;
    ans = sqrt(pf(xd1 - xd2) + pf(yd1 - yd2));
    for (int i = 0; i <= n; i++) {
        ans=min(ans,sqrt(pf(cos(2 * pi*i / n+pi)*r - xd2) + pf(sin(2 * pi*i / n+pi)*r - yd2)) +sqrt(pf(cos(2 * pi*i / n)*r - xd1)+ pf(sin(2 * pi*i / n)*r - yd1)));
    }
    printf("%lf",ans);
}


[编程|1000分] 低位值

时间限制:C/C++ 1秒,其他语言 2秒
空间限制:C/C++ 262144K,其他语言 524288K
64bit IO Format: %lld

题目描述

定义lowbit(x) =x&(-x),即2^(p-1) (其中p为x的二进制表示中,从右向左数第一个1的位置),例如lowbit(10)=2,lowbit(3)=1。
定义函数f(l, r)为(其中0 <= l, r <= n):
301312_1529635925563_722E3A0115F9553EFC8967A62B4C4A7E.png
输入n,求f(l, r)的最大值。

输入描述:

n以二进制形式给出,一行一个二进制01串n,表示l,r的上界。
1 <= 字符串n的长度 <= 20,000
数据保证没有前缀0。

输出描述:

一行一个整数表示答案。

示例1

输入

11

输出

2

说明

二进制串“11”对应的十进制数为“3”

题解

中档题/结论题。当n=1时,r=1,l=0得到的答案为1最大,当n=0时,答案为0。当n大于2时,易知l=1时答案最大。r的取值有两种情况,一是直接取n,二是取n的从左往右第二个1为0,之后均为1.在这两者中取1数量最多的即为符合要求的r。根据此l,r的值算出结果即可。

代码

#include<iostream>
#include<bitset>
#include<string>
#include<string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <stdio.h>
#include <set>
#include <queue>
#include <stack>
using namespace std;
long long ans,ans1,num;
string s;
int main() {
    cin >> s;
    if (s.length() == 1) {
        if (s[0] == '0') {
            cout << 0;
            return 0;
        }
        if (s[0] == '1') {
            cout << 1;
            return 0;
        }
    }
    for (auto i : s) {
        if (i == '0')ans--;
    }
    for (long long i = 2; i <= s.length(); i++) {
        ans += i;
    }

    for (int i = 0; i < s.length();i++) {
        if (s[i] == '1')num++;
        if (num == 2) { s[i] = '0'; num++; }
        else if (num >= 2) { s[i] = '1'; num++; }
    }
    for (auto i : s) {
        if (i == '0')ans1--;
    }
    for (long long i = 2; i <= s.length(); i++) {
        ans1 += i;
    }
    
    

cout << max(ans,ans1);
}

[编程|500分] 开关灯

时间限制:C/C++ 1秒,其他语言 2秒
空间限制:C/C++ 262144K,其他语言 524288K
64bit IO Format: %lld

题目描述

美团的办公室一共有n层,每层有m个会议室,可以看成是一个n*m的网格图。工程师们每天的工作需要协作的地方很多,经常要到会议室开会解决各种问题。公司是提倡勤俭节约的,因此每次会议室只在使用时才开灯。
当一个工程师进入会议室时,假设没有其他人,他会把灯打开。
当一个工程师离开会议室时,假设没有其他人,他会把灯关掉。
现在给出一系列工程师进出会议室的记录,请问在此过程中,最多有多少会议室的灯是亮着的?请输出亮灯数最多时,每个会议室的明暗状态。

输入描述:

第一行三个整数n,m,k,分别表示总行数、总列数、工程师的进出记录数。 接下来k行,每行三个整数和一个字符串x, y, z, t,表示t时间点有一条记录,z=0表示x行y列的会议室有个工程师进入会议室了,z=1表示x行y列的房间有个工程师离开会议室了。
假设一开始所有会议室里都是没人的。 1 <= n, m <= 500 1 <= k <= 100,000
t是HH:MM:SS.SSS的形式,其中HH表示小时,MM表示分钟,SS.SSS表示秒数。(因为工程师有非常强大的时间观念,所以对于他们来说,时间是精确到0.001秒的)
数据保证t在18:00:00.000到23:59:59.999之间,且没有两条记录的时间是完全一样的。数据不保证记录以t升序的形式给出。
1 <= x <= n
1 <= y <= m
z∈{0, 1}
数据保证没有从空会议室离开的情况。
数据保证所有的时间格式合法。HH,MM均为长度为2的字符串,SS.SSS为长度为6的字符串。

输出描述:

输出n行每行m个整数,第i行第j列表示在亮灯数最多的时刻,第i行第j列的会议室的亮灯情况,1表示亮着,0表示没亮。
如果存在多次亮灯数最多的时刻,输出最后一次时的情况。

示例1

输入

2 2 4
1 1 0 18:00:00.000
1 1 1 20:00:00.000
1 1 0 18:00:01.000
1 2 0 18:00:02.000

输出

11
00

题解

简单题。首先按照时间顺序排序,然后依次模拟进出即可。

代码

#include<iostream>
#include<bitset>
#include<string>
#include<string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <stdio.h>
#include <set>
#include <queue>
#include <stack>
using namespace std;
struct jt
{
    int time, n, m, t;
};
bool pd(jt a, jt b) {
    return a.time < b.time;
}
int n, m, k, q1, q2, q3;
int fj[505][505];
int h, mi, s, ms, maxnow;
bitset<300100> now;
bitset<300100> ans;
vector<jt> input;
int num;
int main() {
    cin >> n >> m >> k;
    while (k--) {
        scanf("%d %d %d %d:%d:%d.%d", &q1, &q2, &q3, &h, &mi, &s, &ms);
        input.push_back({ h * 10000000 + mi * 100000 + s * 1000 + ms,q1,q2,q3 });
    }
    sort(input.begin(), input.end(), pd);
    for (auto i : input) {
        if (i.t) {
            fj[i.n][i.m]--;
            if (!fj[i.n][i.m]) {
                num--;
                now.reset(i.n*m + i.m);
            }
        }
        else {
            if (!fj[i.n][i.m]) {
                num++;
                now.set(i.n*m + i.m);
            }
            fj[i.n][i.m]++;
        }
        if (num >= maxnow) {
            ans = now;
            maxnow = num;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (ans[i*m + j])printf("1");
            else printf("0");
        }
        cout << endl;
    }
}

贝壳找房计数比赛

题目链接

2018 计蒜之道复赛--贝壳找房计数比赛

题解

高档题。提议大概是求字符串二在字符串一的全排列中出现的次数。
从字符串一中删去字符串二的个数之后求全排列数再乘以字符串二在字符串一中可能出现的位置数即可。通过乘法逆元避免高精度计算

代码

#include <cstdio>
#include <cstring>
typedef long long ll;
const ll mod=1000000007;
ll qp(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll fac[100005];
char s1[100005],s2[100005],*s,*t;
int cnt[200];
int main(){
    int T,tot;ll ans;
    fac[0]=1;
    for(int i=1;i<=100000;i++)fac[i]=fac[i-1]*i%mod;
    scanf("%d",&T);
    while(T--){
        scanf("%s%s",s=s1,t=s2);
        memset(cnt,0,sizeof(cnt));
        tot=1;
        while(*s)cnt[*s++]++,tot++;
        while(*t)cnt[*t++]--,tot--;
        ans=fac[tot];
        for(int i='a';i<='z';i++){
            if(cnt[i]<0){ans=0;break;}
            if(fac[cnt[i]]!=1)ans=ans*qp(fac[cnt[i]],mod-2)%mod;
        }
        printf("%lld\n",ans);
    }
}

贝壳找房函数最值

题目链接

2018 计蒜之道复赛--贝壳找房函数最值

题解

简单题。题意大概是给定多组f(x)=ax+b中a,b的值,求将这些函数嵌套后的最大值。
先排序然后一个个算即可

代码

#include<iostream>
#include<bitset>
#include<string>
#include<string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <stdio.h>
#include <set>
#include <queue>
#include <stack>
using namespace std;
const int N = 10005;
int t, n, x;
pair<int, int> a[N];
bool pd(pair<int, int> a, pair<int, int> b) {
        return a.first*b.second+a.second < b.first*a.second+b.second;    
}
int main() {
    cin >> t;
    for (; t; t--) {
        cin >> n >> x;
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; i++) {
            cin >> a[i].first;
        }
        for (int i = 1; i <= n; i++) {
            cin >> a[i].second;
        }
        sort(a + 1, a + n + 1, pd);
        for (int i = 1; i <= n; i++) {
            x = (x*a[i].first + a[i].second) % 10;
        }
        cout << x << endl;
    }
}

E. Careful Maneuvering

题目链接

Codeforces Round #488 by NEAR (Div. 2)--E. Careful Maneuvering

题解

中档题。题意大概是在x=100与x=-100处有多架敌机,我方在x=0处有两架小飞机,敌机会在同一时刻同时向两家小飞机发动攻击,求最大可摧毁的敌机数量。
枚举每一点敌机击落情况,使用bitset找出和最大的两个位置即可。

代码

#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
using namespace std;

vector<int> l;
vector<int> r;
int q1, q2, m, n, ans;
vector<bitset<125>>des;
set<bitset<125>>same;
bitset<125>temp;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> q1;
        l.push_back(q1 * 2);
    }
    sort(l.begin(), l.end());
    for (int i = 0; i < m; i++) {
        cin >> q1;
        r.push_back(q1 * 2);
    }
    sort(r.begin(), r.end());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int now = (l[i] + r[j]) / 2;
            temp.reset();
            for (int k = 0; k < n; k++) {
                for (q2 = 0; q2 < m; q2++) {
                    if (r[q2] == now + now - l[k]) {
                        temp.set(k);
                        temp.set(q2 + 60);
                    };
                }
            }
            des.push_back(temp);
        }
    }
    for (auto i : des) {
        for (auto j : des) {
            temp = i | j;
            ans = max(ans, (int)temp.count());
        }
    }
    cout << ans;
}

C. Two Squares

题目链接

Codeforces Round #488 by NEAR (Div. 2)--C. Two Squares

题解

简单题。题意大概是给定两个正方形,一个边平行于坐标轴,另一个边与坐标轴成45度。求这两个正方形有无公共部分(一个点也算)。
因为数据规模并不大,判断某一正方形中的每一点有没有出现在另一正方形即可。

代码

#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int q1, q2, q3, q4, q5, q6, q7, q8;
pair<int,int> w[5],u,d,l,r;

int main() {
    cin >> q1 >> q2 >> q3 >> q4 >> q5 >> q6 >> q7 >> q8;
    cin >> w[1].first >> w[1].second >> w[2].first >> w[2].second >> w[3].first >> w[3].second >> w[4].first >> w[4].second;
    sort(w + 1, w + 5);
    l = w[1];
    r = w[4];
    u = w[2].second > w[3].second ? w[2] : w[3];
    d = w[2].second < w[3].second ? w[2] : w[3];
    bool ans=false;
    for (int x = min(min(q1, q3), min(q5, q7)); x <= max(max(q1, q3), max(q5, q7)); x++) {
        for (int y = min(min(q2, q4), min(q6, q8)); y <= max(max(q2, q4), max(q6, q8)); y++) {
            if (x <= u.first) {
                if (y <= l.second + x - l.first&&y >= l.second - x + l.first)ans = true;
            }
            else {
                if (y <= r.second - x + r.first&&y >= r.second + x -r.first)ans = true;
            }
        }
    }
    if (ans) cout << "YES";
    else cout << "NO";
}

B. Knights of a Polygonal Table

题目链接

Codeforces Round #488 by NEAR (Div. 2)--B. Knights of a Polygonal Table

题解

简单题。题意大概是有一组武士,每个可以杀掉k个比自己武力值低的其他武士,每个武士有一定金币,杀掉其他武士可以获得他的金币。求每个武士可能获得的最大金币。
将武力值排序后用优先队列维护金币数量即可,注意最终答案较大,应使用long long。

代码

#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int n, k;
pair<int,int> a[100005];
priority_queue<int> que;
priority_queue<int> temp;
int mon[100005];
long long ans[100005];
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        a[i].second = i;
        cin >> a[i].first;
    }
    for (int i = 1; i <= n; i++) {
        cin >> mon[i];
        ans[i] = mon[i];
    }
    sort(a + 1, a + n + 1);
    que.push(mon[a[1].second]);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; (j <= k)&&que.size(); j++) {
            ans[a[i].second] += que.top();
            temp.push(que.top());
            que.pop();
        }
        for (; temp.size();) {
            que.push(temp.top());
            temp.pop();
        }
        que.push(mon[a[i].second]);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
}

A. Fingerprints

题目链接

Codeforces Round #488 by NEAR (Div. 2)--A. Fingerprints

题解

简单题,题意大概是给定两串序列,按序列一中的顺序输出序列二中的数。
因为数据规模非常小,直接标记序列二中出现的数在序列一中按顺序输出即可。

代码

#include <iostream>
using namespace std;
int n, m,a[15],q1;
bool b[15];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> q1;
        b[q1] = true;
    }
    for (int i = 1; i <= n; i++) {
        if (b[a[i]])cout << a[i] << ' ';
    }
    cout << endl;
}

C. A Mist of Florescence

题目链接

Codeforces Round #??487(Div. 2)--C. A Mist of Florescence

题解

简单题/难题(也可能是傻逼题)。题意大概是使用四种颜色对一块区域染色,使每种颜色的联通块的数量为所要求的数量。
乍一看好像很麻烦的样子,实际上注意到数据规模,每种颜色的联通块的数量至少为1,至多为100,而允许的区域数量有50*500,那就可以玄学AC了。首先对四种颜色各染一大块,然后往第一种颜色里填充第二种颜色,第二种颜色里填充第三种颜色,以此类推直到符合要求即可。

代码

#include <cstdio>
#include <cmath>
#include <iostream>
#include <string.h>
#include <string>
using namespace std;
char s[55][55];
int a, b, c, d;
int main() {
    cin >> a >> b >> c >> d;
    a--;
    b--;
    c--;
    d--;
    for (int i = 0; i < 50; i++) {
        for (int j = 0; j < 50; j++) {
            if (i / 12 == 0) s[i][j] = 'A';
            else if (i / 12 == 1) s[i][j] = 'B';
            else if (i / 12 == 2) s[i][j] = 'C';
            else s[i][j] = 'D';
        }
    }
    int temp = 0;
    for (int i = 1; i <= 10; i+=2) {
        for (int j = 1; j < 49; j++) {
            if (!d)break;
            temp++;
            if (temp % 2) { s[i][j] = 'D'; d--; }
        }
    }
    temp = 0;
    for (int i = 13; i <= 22; i+=2) {
        for (int j = 1; j < 49; j++) {
            if (!a)break;
            temp++;
            if (temp % 2) { s[i][j] = 'A'; a--; }
        }
    }
    temp = 0;
    for (int i = 25; i <= 37; i+=2) {
        for (int j = 1; j < 49; j++) {
            if (!b)break;
            temp++;
            if (temp % 2) { s[i][j] = 'B'; b--; }
        }
    }
    temp = 0;
    for (int i = 37; i <= 47; i+=2) {
        for (int j = 1; j < 49; j++) {
            if (!c)break;
            temp++;
            if (temp % 2) { s[i][j] = 'C'; c--; }
        }
    }
    cout << 50 << ' ' << 50 << endl;
    for (int i = 0; i < 50; i++) {
        cout << s[i] << endl;
    }
}