《寒假每日一题 2022》

1960. 闪烁

重点分析

  • 状态压缩：将二进制转化为十进制
  • 状态转移：在十进制状态下进行转移
    	int last = num & 1; 
	int temp = (num >> 1) + (last << n - 1); 
	num = num ^ temp;
  • 计算答案（容易出错，算明白了再写，尤其注意T=1的情况）

Ac代码

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

map st;
map tt;
map ans;
ll n, t;

int main()
{
    scanf("%lld%lld", &n, &t);
    ll num = 0;
    for(int i = 0; i < n; i ++){
        int x;
        scanf("%d", &x);
        num = num * 2 + x;
    }
    //st[num] = true;
    //tt[num] = 0;
    //ans[0] = num;
    
    bool flag = true;
    int stop = 0;
    for(int i = 1; i <= t; i ++){
        int last = num & 1; 
        int temp = (num >> 1) + (last << n - 1); 
        num = num ^ temp; 
        //cout << num  << endl;
        if(st[num]) {
            stop = i;
            flag = false;
            break;
        }
        st[num] = true;
        tt[num] = i;
        ans[i] = num;
    }
    if(flag == false){
        ll tag = tt[num];
        ll T = stop - tag;
        ll res;
        if(T == 1) res = stop - 1;
        else res = (t - tag + 1) % T + tag - 1;
        //cout << tag << ' ' << t << ' ' << stop << endl;
        num = ans[res];
    }

    for(int i = n - 1; i >= 0; i --){
        int x = (num >> i) & 1;
        printf("%d\n", x);
    }
    return 0;
}

1945. 奶牛棒球

题目链接
https://www.acwing.com/problem/content/1947/
解析
暴力枚举x、z(z > x），二分查找是否有满足条件的y，一直x、z后y的范围很容易推。
y的范围可以用double表示，不用考虑取整问题。
Ac代码

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1010;

typedef long long ll;

int a[N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    
    ll ans = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = i + 1; j <= n; j ++){
            int x = a[i], z = a[j];
            //cout << x << ' ' << z << endl;
            double left = (double)(2 * x + z) / 3.0, right = (double)(x + z) / 2.0;
            //cout << left << ' ' << right << endl;
            int l = i, r = j;
            while (l < r) {
                int mid = l + r >> 1;
                if ((double)a[mid] >= left) r = mid;
                else l = mid + 1;
            }
            int ll = l;
            l = i, r = j;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if ((double)a[mid] <= right) l = mid;
                else r = mid - 1;
            }
            int rr = l;
            //cout << ll << ' ' << rr << endl;
            ans += max(0, rr - ll + 1);
            //puts("");
        }
    }
    printf("%lld\n", ans);
    
    return 0;
}

1934. 贝茜放慢脚步

题目链接
https://www.acwing.com/problem/content/1936/
解析
问题的本质是做一个两路归并，写代码的时候要明确需要维护的值，对于每一个要减慢速度的点，我们应当记录在减慢速度前已消耗的时间T和已走过的路程S，同时注意中有round（double x）函数方便进行四舍五入。

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e4 + 10;

double tt[N], dd[N];
double T, S;
char op;
int tidx, didx, n;

int main()
{
    scanf("%d\n", &n);
    while(n --){
        double x;
        scanf("%c %lf\n", &op, &x);
        //cout << op << ' ' << x << endl;
        if(op == 'T') tt[tidx ++] = x;
        else dd[didx ++] = x;
    }
    sort(tt, tt + tidx);
    sort(dd, dd + didx);
    
    int k = 1, i = 0, j = 0;
    while(i < tidx && j < didx){
        double td = (dd[j] - S) * k;
        if(td < tt[i] - T){
            T += td;
            S = dd[j];
            k ++, j ++;
        }
        else{
            S += (tt[i] - T) / (double)k;
            T = tt[i];
            k ++, i ++;
        }
    }
    while(i < tidx){
        S += (tt[i] - T) / (double)k;
        T = tt[i];
        k ++, i ++;
    }
    while(j < didx){
        T += (dd[j] - S) * k;
        S = dd[j];
        k ++, j ++;
    }
    T += (1000 - S) * k;
    printf("%.0lf\n", round(T));
    return 0;
}

1922. 懒惰的牛

题目链接
https://www.acwing.com/activity/content/problem/content/6539/

解析

  • 注意\(x_i\)的范围不利于做前缀和处理，所以整体+1
  • 有点离散话的意思，不要把数据范围看花眼了
  • mmax好像不可以用N直接替代，感觉有点奇怪。。。
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 1e7 + 10;

int a[N];
ll s[N];
int n, k;

int main()
{
    scanf("%d%d", &n, &k);
    int mmax = 0;
    for(int i = 1; i <= n; i ++) {
        int x, y;
        scanf("%d%d", &y, &x);
        a[x + 1] = y;
        mmax = max(mmax, x + 1);
    }
    for(int i = 1; i <= mmax; i ++) s[i] = s[i - 1] + a[i];
    ll ans = 0;
    for(int i = 1; i <= mmax; i ++){
        int l = max(1, i - k), r = min(mmax, i + k);
        ans = max(ans, s[r] - s[l - 1]);
    }
    printf("%lld\n", ans);
    
    return 0;
}

1913. 公平摄影

题目链接
https://www.acwing.com/problem/content/1915/

解析
题目表述不清晰，关于题目的分析：
https://www.acwing.com/solution/content/85524/

具体做法：
比较巧妙的一点是将两种牛的tag设置为1、-1，原题转化为哪些段的和为0，有两种情况：

  • s[i] = 0, 从第一头牛到第i头牛和为0

  • s[i] = s[j] ！= 0, 从 i + 1 到 j 和为 0

这两种情况可以合并，可以通过设s[0] = 0实现

由于数据范围问题，通过pair和map来存储数据；

只包含一种牛的情况用双指针来做，代码写的不够熟练，主要是由于对于循环终止状态不够清晰。

Ac代码

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;
typedef pair PII;

int n;
PII a[N];
ll s[N];
map st;
map pos;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        ll x;
        char op;
        scanf("%lld %c\n", &x, &op);
        if(op == 'G') a[i] = {x, 1};
        else a[i] = {x, -1};
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i ++)
        s[i] = s[i - 1] + a[i].second;
        //printf("%d ", s[i]);  //s的范围是1-n
    
    ll ans = 0;
    for(int i = 1; i <= n; i ++){
        if(s[i] == 0) ans = max(ans, a[i].first - a[1].first);
        else{
            if(!st[s[i]]) {
                st[s[i]] = true;
                pos[s[i]] = i;
            }
            else{
                ans = max(ans, a[i].first - a[pos[s[i]] + 1].first);
            }
        }
    }
    
    ll res = 0, i = 1;
    while(i <= n && a[i].second != -1) i ++;
    while(i <= n){
        int j = i;
        while(j <= n && a[j].second != 1) j ++;
        res = max(res, a[j - 1].first - a[i].first);
        //printf("%lld ", res);
        while(j <= n && a[j].second != -1) j ++;
        i = j;
    }
    ans = max(ans, res);
    
    res = 0, i = 1;
    while(i <= n && a[i].second != 1) i ++;
    while(i <= n){
        int j = i;
        while(j <= n && a[j].second != -1) j ++;
        res = max(res, a[j - 1].first - a[i].first);
        //printf("%lld ", res);
        while(j <= n && a[j].second != 1) j ++;
        i = j;
    }
    ans = max(ans, res);
    //puts("");
    //printf("%lld %lld\n", ans, res);
    printf("%lld\n", ans);
    
    return 0;
}

1904. 奶牛慢跑

题目链接
https://www.acwing.com/activity/content/problem/content/6541/

解析
用栈挺好的，但是懒得搞了，写了个离散化for了一遍也可以

Ac代码

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

typedef pair PII;

int n;
PII a[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        int x, v;
        scanf("%d%d", &x, &v);
        a[i] = {x, v};
    }
    int cnt = 0, vv = a[n].second;
    for(int i = n; i >= 1; i --){
        if(a[i].second <= vv) cnt ++;
        vv = min(vv, a[i].second);
    }
    printf("%d\n", cnt);

    return 0;
}
ACM

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签