分类 其他 下的文章

随着题目越做越多,每次都写题解感觉有些力不从心(恩这就是鸽了这么久的理由),再加上主力写代码的设备从台式机迁移到pixelbook。

以后的程序等代码均备份到github水题记录上,有空的时候补上题解,没空的时候仅保存代码。

文件最前方加上下划线的为暂时(也可能是永久(咕咕咕))没有AC的代码。

以上

Army Game

题目链接

HackerRank - game-with-cells -- Army Game

题解

简单题。题意大概是在平面内有n*m个房子分布在单元格内,求最少建设补给站的数目使得所有的房子均与至少一个补给站相连。
建在角落处的补给站可以与四个房子相连,依次方式建设的补给站数目最少。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

long long ans;
ll gcd(ll a,ll b){
    if (b!=0) ans+=a/b;
    return b?gcd(b,a%b):a;
}
long long a,b;
int main() {
    cin>>a>>b;
    cout<<((a+1)/2)*((b+1)/2);
}

Lounge Lizards

题目链接

2017 United Kingdom and Ireland Programming Contest (UKIEPC 2017)

题解

中档题。题意大概是一群人(蜥蜴)看一个电视,如果电视与两个人在同一直线上且后面的人严格高于前面的才不会被挡住。问移除若干人(也可以不移除)后最多有多少人可以同时看电视且不会被挡住?
以电视为中心,对每个方向上的人的高度做LIS,之后将这些最长上升序列的元素个数相加即可。由于考虑到可能存在的精度问题,我并没有使用浮点数表示方向,而是使用x和y除去最大公约数后的值表示方向。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const int inf = (1 << 31) - 1;
const ll INF = 1ll << 60;

int tx, ty, n;
int q1;
struct Input {
    int x, y, flag, h;
}input[MAXN];
pair<int, pair<int, int>> temp;
set<pair<int, pair<int, int>>> pd;
map<pair<int, pair<int, int>>, vector<int>> nowh;

int dp[MAXN];

int lis(vector<int>&a){
    memset(dp, 0x3f, sizeof(int)*a.size());
    int len = 1;
    dp[0] = a[0];
    for (int i = 1; i < a.size(); ++i)    {
        int pos = lower_bound(dp, dp + len, a[i]) - dp;
        dp[pos] = a[i];
        len = max(len, pos + 1);
    }
    return len;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

pair<int, pair<int, int>> tran(Input a) {
    q1 = gcd(a.x, a.y);
    temp.first = a.flag;
    temp.second.first = a.x / q1;
    temp.second.second = a.y / q1;
    return temp;
}

inline bool eq(Input a, Input b) {
    return a.flag == b.flag&&a.h == b.h&&a.x == b.x&&a.y == b.y;
}

inline bool cmp(Input a, Input b) {
    return (a.flag == b.flag ? (a.x == b.x ? (a.y < b.y) : a.x < b.x) : a.flag < b.flag);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> tx >> ty >> n;
    for (int i = 1; i <= n; i++) {
        cin >> input[i].x >> input[i].y >> input[i].h;
        input[i].x -= tx;
        input[i].y -= ty;
        input[i].flag = (input[i].x > 0) * 233 + (input[i].y > 0);
        input[i].x = abs(input[i].x);
        input[i].y = abs(input[i].y);
    }
    sort(input + 1, input + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        tran(input[i]);
        nowh[temp].push_back(input[i].h);
    }
    int ans = 0;
    for (auto i : nowh) {
        ans += lis(i.second);
    }
    cout << ans << endl;
}

Blast the Enemy!

题目链接

[UVALive 4426] Blast the Enemy!

题解

中档题。题目看起来很复杂实质上是求多边形的中心。
模板题。

代码

#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;

const int MAXN = 105;
int N;
double S[110];
struct Point{
    double x, y;
    Point(){}
    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }
    Point operator + (const Point& b) {
        return Point(x + b.x, y + b.y);
    }
    Point operator - (const Point& b) {
        return Point(x - b.x, y - b.y);
    }
    Point operator * (const double &b) {
        return Point(x*b, y*b);
    }
    Point operator / (const double &b) {
        return Point(x / b, y / b);
    }
}input[MAXN];

double cross(Point a, Point b) {
    return a.x*b.y - a.y*b.x;
}
double area(Point a, Point b, Point c) {
    return cross(b - a, c - a);
}


int main() {
    int T = 1;
    while ((cin >> N) && N) {
        for (int i = 1; i <= N; i++) {
            cin >> input[i].x >> input[i].y;
        }
        S[0] = 0;
        Point temp(0, 0);
        for (int i = 2; i<N; i++) {
            S[i] = area(input[1], input[i], input[i + 1]); S[0] += S[i];
            temp = temp + ((input[1] + input[i] + input[i + 1]) / 3.0)*S[i];
        }
        temp = temp / S[0];
        cout << "Stage #" << T++ << ": ";
        cout << fixed << temp.x << ' ' << fixed << temp.y << endl;
    }
}

[编程|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;
    }
}

贝壳找房移山(简单/中等)

题目链接

贝壳找房移山(简单)
贝壳找房移山(中等)

题解

中档题。由于每次移山是将连续的一段山顶移除1个单位的高度,只需提取出所有的山顶与山谷的高度来减少运算量。
之后每次贪心找出并抹去一个消耗最少的山顶即可。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#define maxxx(a,b) (a>b?a:b)
#define ll long long
using namespace std;
ll n, k,t;
ll a;
vector<ll> high;
int main() {
    cin >> t;
    for (ll q = 1; q <= t; q++) {
        cin >> n >> k;
        ll last = 0, ans = 0;
        high.clear();
        bool which = true;//true 找峰,false找谷底
        high.push_back(0);
        for (ll i = 1; i <= n; i++) {
            cin >> a;
            if (which) {
                if (a < last) {
                    high.push_back(last);
                    which = false;
                }
            }
            else {
                if (a > last) {
                    high.push_back(last);
                    which = true;
                }
            }
            last = a;
        }
        if (which == true) {
            high.push_back(last);
            high.push_back(0);
        }
        else
            high.push_back(0);
        ll numofsf = high.size() / 2;
        for (ll i = 1; i <= numofsf-k; i++) {
            ll willdel = 1;
            for (ll j = 1; j <= high.size() / 2; j++) {
                if (high[j * 2 - 1] - (maxxx(high[j * 2 - 2], high[j * 2])) < high[willdel] - maxxx(high[willdel - 1], high[willdel + 1]))
                    willdel = j * 2 - 1;
            }
            if (high[willdel + 1] > high[willdel - 1]) {
                ans += high[willdel] - high[willdel + 1];
                high.erase(high.begin() + willdel);
                high.erase(high.begin() + willdel);
            }
            else {
                ans += high[willdel] - high[willdel - 1];
                high.erase(high.begin() + willdel-1);
                high.erase(high.begin() + willdel-1);
            }
        }
        cout << ans<<endl;
    }
}