2020.09.13

CF 670div2 - B

题意:给一串数,可以有正有负,找出五个数使得相乘后结果最大。
地址
思路:双指针,将这串数排序,在两端选择数,保证两端的个数x + y = 5即可。

2020.09.14

CF 669div2 - A

题意:给一串0,1数,去掉最多一半的数后,使得数串的奇数偶数项分别的和相等。
地址
思路:判断0和1的个数,如果1的个数全部小于0则将1全去掉,否则去掉全部0后

  1. 如果1的个数为偶数,则直接输出
  2. 否则输出1的个数-1个1

2020.09.17

CF 668dv2 - A

题意:给一串数O(包含连续自然数且每个出现一次),求另一串数使得相邻两项的和的数与所给的数的相邻项之和的数都相等。
地址
思路:把原数串从后往前输出就好了...不要想太多。

CF 668div2 - C

题意:给01数串(包含未知01的'?'),问是否可以任意连续k个都是0和1各二分之一。
地址
思路:看前k个,且后序间隔k对应的字符要和前k个中的相等。(滑窗划入的和划出的要相同)同时判断k个中的0和1是否超过k/2.(这里不需要管'?',因为自动认为'?'是最佳结果)

2020.09.19

[补9.18晚]

CF 666div2 - B

题意:给一串数,可以随意排序,看将每个数加或减几次才能变成c的幂序列。求最小的次数。
地址
思路:暴力求解,从小到大排序后,求c不同时需要增减的次数。经ljy大佬的提醒,有三点需要注意:

  1. 指数增长飞快,可以断定在n>50左右时一定是全1情况为解。
  2. 暴力break的地方不应该是now > ans的时候,因为不可以保证一定是线性的,可以有小,大,更小的情况。而应该是暴力到数超过范围了为止。
  3. abs()和pow()最好不一起用,容易出问题,还有min()也最好自己用if写....
#include <bits/stdc++.h>
typedef int64_t ll;
using namespace std;
const ll inf=1e18;

int main()
{
    ll n;
    cin>>n;
    ll num[n];
    ll sum = 0;
    for(ll i = 0;i < n;i++) {
        cin>>num[i];
        sum += num[i];
    }
    if(n >= 50) {
        cout<<sum - n;
        return 0;
    }
    sort(num,num + n);
    ll ans = inf;
    int flag = 1;
    for(ll k = 2;k <= 100000;k++){
        ll tmp = 0;
        ll Tmppow = 1;
        for(ll i = 0;i < n;i++){
            //这里如果超出范围break 
            if(Tmppow > 1e14){
                flag = 0;
                break;
            }
               tmp += abs(num[i] - Tmppow);
               Tmppow *= k;
        }
        if(!flag) break;
        if(ans > tmp){
            ans = tmp;
        }
    }
    ans = min(sum - n,ans);
    cout<<ans;
}

当时错误的思路 & 代码

错误思路:从小到大排序后,暴力求c不同时需要增减的次数。注意在发现比当前大时直接break。

#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
int main()
{
    int n;
    cin>>n;
    ll num[n];
    for(int i = 0;i < n;i++) cin>>num[i];
    sort(num,num + n);
    ll ans;
    for(int k = 1;k <= 100000;k++){
        ll tmp = 0;
        for(int i = 0;i < n;i++){
            tmp += abs(num[i] - pow(k,i));
            if(k != 1 && tmp > ans) break;
        }
        if(k == 1) ans = tmp;
        else ans = min(tmp,ans);
    }
    cout<<ans;
}

CF 666div2 - C

题意:给一串数,只能做3次改动使得最后每位上都为0。改动时需要将所给数串中连续子串的每一位加上子串长度的倍数
地址
思路:数学问题想特数情况
设一共n个数,这里n == 5:

lenabcde
1n-1 (n-1) * b(n-1) * c(n-1) * d(n-1) * e
2n-n * a-n * b-n * c-n * d-n * e
311 a (n-1)
00000

2020.09.22

CF 671 div2

需要注意在计算值为long long 时中间变量也要写成ll,不能用int!
(今天好开心!睡觉睡觉

2020.09.24

CF 665div2 - C

题意:给一串数,当两个数的最大公约数gcd与所有数中的最小值相等时则可以交换,问经过多次交换后可否所有数递增。
地址
思路:将所有数排序,与原来的比较,位置不同的则%min,如果不为0,则NO,反之,YES。
错误思路:不能先都%min再将!=0的排序看是否递增。因为可能可以交换的数无法交换到正确的位置上。如:2435 [x]
doge(日常被巨佬吊打)
dl

2020.10.19

CF 4div2 - A

注意一个数N可以分成两个偶数需要

  1. N是偶数
  2. N大于2

CF 450B

地址
img
看到这种要找规律,否则暴力会超时的。
找规律可以看出:F(n) : {x, y, y - x,  - x,  - y, x - y, x, y, y - x, ...}

2020.11.08

CF 1437B

题意:给一个01串,问最少几次成段交换可以得到01交替的串。
地址
思路
11101000如果有连续的数字,就需要翻转子字符串。而显然这里划线的最后一位必须和下划线的第一位不同,并且最后一位数字也是有连续的数字的,这样翻转才能做到一石二鸟,是翻转次数尽可能地少。
这样虽然讲得通,但是似乎略显麻烦。再观察观察,前三个连续的1,在进行一次翻转后,依旧有两个1是相邻的,那这两个1肯定又需要一次翻转,使之分离。可以这样理解,一段连续的数字,需要翻转的次数是其长度减去1的值
总结一下就是,需要翻转的次数等于字符串中所有连续的1(或0)的长度减一的和。
但是又发现第二个例子0110,如果只考虑0,结果是错的,但是只考虑1就是对的。既然这样就干脆0和1都分别单独考虑,取最大值。

2020.11.19

LC - 279. 完全平方数

题意:找出一个数可以拆成最小多少个完全平方数。
地址
思路:动规,dp[i] = MIN(dp[i], dp[i - j * j] + 1),i 表示当前数字,j*j 表示平方数

代码在此

class Solution {
public:
    int numSquares(int n) {
        int dp[n+1];
        memset(dp,0,sizeof(dp));
        for(int i = 1;i <= n;i++){
            dp[i] = i;
            for(int j = 1;j * j <= i;j++){
                dp[i] = min(dp[i],dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
};

2020.11.23

LC - 452. 用最少数量的箭引爆气球

地址
关键:给了好几个线段,求用最少的点覆盖这些区间。(点在区间里即为覆盖)
思路:贪心,按左端点排序,首先pos为第一个的右端点,依次往下寻找

  • 如果下一个区间左端点 <= pos,计数不变,更新pos = min(pos,右端点)
  • 如果下一个区间左端点 > pos,计数 ++ ,pos = 右端点。

其他:和之前贪心训练时候的小岛放炸弹的题一样。

2020.12.01

CF 222div1-A

地址
题意:.是路,#是墙,想再放k个墙(输出时标记为X)使得最后的路仍然为联通路径,问放X(墙)后的矩阵长啥样
思路:刚开始看这道题头大的很,后来发现可以先让所有路.都变成X,再BFS个cnt-k次(把经过的标记回.)(cnt为原来.的个数)

代码在此

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

int N[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};

int main()
{
    int m,n,k;
    cin>>m>>n>>k;
    char Maze[m][n];
    int cnt = 0;
    int startx = 0;
    int starty = 0;
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            cin>>Maze[i][j];
            if(Maze[i][j] == '.') {
                Maze[i][j] = 'X';
                cnt ++ ;
                startx = i;
                starty = j;
            }
        }
    }
    cnt -= k;
    if(cnt == 0){
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                cout<<Maze[i][j];
            }
            cout<<endl;
        }
        return 0;
    }
    queue<pair<int,int>> Que;
    Que.push(pair<int,int>(startx,starty));
    Maze[startx][starty] = '.';
    cnt -- ;
    if(cnt == 0){
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                cout<<Maze[i][j];
            }
            cout<<endl;
        }
        return 0;
    }
    bool ok = false;
//    for(int i = 0;i < m;i++){
//        for(int j = 0;j < n;j++){
//            cout<<Maze[i][j];
//        }
//        cout<<endl;
//    }
    while(Que.size()){
        int nowx = Que.front().first;
        int nowy = Que.front().second;
        Que.pop();
        for(int i = 0;i < 4;i++){
            int tmpx = nowx + N[i][0];
            int tmpy = nowy + N[i][1];
            if(tmpx >= 0 && tmpx < m && tmpy >= 0 && tmpy < n && Maze[tmpx][tmpy] == 'X'){
                Que.push(pair<int,int>(tmpx,tmpy));
                Maze[tmpx][tmpy] = '.';
//                for(int i = 0;i < m;i++){
//                    for(int j = 0;j < n;j++){
//                        cout<<Maze[i][j];
//                    }
//                    cout<<endl;
//                }
//                cout<<cnt<<"-------------------\n";
                cnt--;
                if(cnt == 0) {
                    ok = true;
                    break;
                }
            }
        }
        if(ok) break;
    }
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            cout<<Maze[i][j];
        }
        cout<<endl;
    }
    return 0;
}
/*
3 3 8
...
...
...
*/

Last modification:December 1st, 2020 at 09:15 pm
请赏我杯奶茶,让我快乐长肉