爱宣纸
1小时前

字符串流做法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>

using namespace std;

int main()
{
    string s, c;
    getline(cin, s);

    s.pop_back();//直接去掉末尾的英文句号
    stringstream ssin(s);//引入字符串流读入句中的单词

    string str;
    int cnt = 0;
    //逐个判断每个单词,得出最长的单词
    while (ssin >> str) if (str.length() > cnt) cnt = str.length(), c = str;

    cout << c << endl;
    return 0;

}



截屏2022-12-09 01.35.48.png

代码

import java.util.*;
import java.io.*;

public class Main {
    static int N = 100010, n, idx;
    /**
     * 邻接表存点边关系
     */ 
    static int[] h = new int[N];
    static int[] e = new int[2 * N];
    static int[] ne = new int[2 * N];
    /**
     * 节点染色数组,0 表示未染色,1 表示集合A染色,2 表示集合B染色
     */ 
    static int[] co = new int[N];
    /**
     * 点边关系存入邻接表
     */ 
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    /**
     * DFS 染色,返回值为当前染色过程是否有冲突。有 返回 true,没有返回 false
     */ 
    static boolean dfs(int u, int c) {
        // 给当前点染色
        co[u] = c;
        // 遍历当前点的所有连接点
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            // 如果连接点未染色
            if (co[j] == 0) {
                // 给连接点 DFS 染色,色彩要与当前点不同。如果染色过程有冲突,则返回 true
                if (dfs(j, 3 - c)) return true;
            }
            // 如果连接点已染色,并且与当前点色彩一致。则表示染色有冲突,返回 true
            else if (co[j] == c) return true;
        }
        // 染色无误,返回 false
        return false;
    }

    /**
     * 染色检查
     */ 
    static boolean check() {
        boolean f = true;
        // 遍历所有点
        for (int i = 1; i <= n; i ++) {
            // 如果当前点没有染色
            if (co[i] == 0) {
                // 进行 DFS 染色,如果染色过程有冲突,则表示不是二分图,返回 false
                if (dfs(i, 1)) {
                    f = false;
                    break;
                }
            }
        }
        // 返回二分图判断
        return f;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        n = sc.nextInt();
        int m = sc.nextInt();
        Arrays.fill(h, -1);
        while (m -- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a, b);
            add(b, a);
        }
        System.out.println(check() ? "Yes" : "No");
        sc.close();
    }
}



Samuely
2小时前
python依旧简单
s1 = input()
s2 = input()
s3 = input()

for word in s1.split(" "):
    if word == s2:
        print(s3, end=' ')
    else:
        print(word, end=' ')

自从学了stringstream做字符串就开心多了
#include<iostream>
#include<sstream>
using namespace std;

int main()
{
    string s1, s2, s3;
    getline(cin, s1);
    cin >> s2 >> s3;

    stringstream ssin(s1);

    string word;
    while(ssin >> word)
    {
        if (word == s2) cout << s3 << ' ';
        else cout << word << ' ';
    }

    return 0;
}



Samuely
2小时前
这么写真简单
#include<iostream>
using namespace std;

int main()
{   
    string srr[100];

    int n = 0;
    while(cin >> srr[n]) n++;

    for(int i=n-1; i>=0; i--) cout << srr[i] << ' ';

    return 0;
}
强行回忆起了vector
#include<iostream>
#include<sstream>
#include<vector>
using namespace std;

int main()
{
    string str;
    getline(cin, str);
    stringstream ssin(str);
    vector<string> sv;

    string word;
    int num = 0;
    while(ssin >> word)
    {
        sv.push_back(word);
        num += 1;   
    }

    for(int i=sv.size()-1; i>=0; i--) cout << sv[i] << ' ';

    return 0;
}
python 依旧简单
str_list = input().split(' ')
for i in range(len(str_list)-1, -1, -1):
    print(str_list[i], end=' ')



tomousw
2小时前

吃奶酪

题目描述

房间里放着 $n$ 块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在 $(0,0)$ 点处。

输入格式

第一行有一个整数,表示奶酪的数量 $n$。

第 $2$ 到第 $(n + 1)$ 行,每行两个实数,第 $(i + 1)$ 行的实数分别表示第 $i$ 块奶酪的横纵坐标 $x_i, y_i$。

输出格式

输出一行一个实数,表示要跑的最少距离,保留 $2$ 位小数。

样例 #1

样例输入 #1

4
1 1
1 -1
-1 1
-1 -1

样例输出 #1

7.41

提示

数据规模与约定

对于全部的测试点,保证 $1\leq n\leq 15$,$|x_i|, |y_i| \leq 200$,小数点后最多有 $3$ 位数字。

提示

对于两个点 $(x_1,y_1)$,$(x_2, y_2)$,两点之间的距离公式为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。


$2022.7.13$:新增加一组 $\text{Hack}$ 数据。

尝试bfs,开O2优化居然过了,离谱,

切记状态要记录齐,必须记录当前位置和已经走过的位置,不能忽略任何一个,否则就是逻辑漏洞

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

unordered_map<int,double> dist;
pdd a[21];
int n;

int spc(int x,int seq){//手动哈希
    return x+(seq+1)*1e6;
}

double get_d(pdd a,pdd b){
    double dx=a.first-b.first;
    double dy=a.second-b.second;
    return sqrt(dx*dx+dy*dy);
}

void bfs(){
    dist[spc((1<<n)-1,20)]=0;//设置一个不会冲突的20作为(0,0)点
    queue<pii> q;
    q.push({(1<<n)-1,20});
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        int x=t.first;
        pdd old_pd=a[t.second];
        for(int i=0;i<n;i++){
            if(x>>i&1){
                int nx=x-(1<<i);
                double nd= get_d(old_pd,a[i]);
                if(dist.count(spc(nx,i))==0  ||dist[spc(nx,i)]>dist[spc(x,t.second)]+nd){
                    dist[spc(nx,i)]=dist[spc(x,t.second)]+nd;
                    q.push({nx,i});
                }
            }
        }
    }
}

int main(){
    cin>>n;
    a[20]={0,0};
    for(int i=0;i<n;i++)cin>>a[i].first>>a[i].second;
    bfs();
    double ans=1e19;
    for(int i=0;i<n;i++)ans=min(ans,dist[spc(0,i)]);
    printf("%.2lf",ans);
    return 0;
}

明天补DP和dfs方法




gainorlose
2小时前

N = eval(input())
list1 = []
stat = {}
for i in range(N):
hang = input().split()
for j in hang:
list1.append(eval(j))
list1.sort(reverse = True)

for ch in range(list1[-1],list1[0] + 1):
stat[str(ch)] = 0

for i in list1:
stat[str(i)] += 1

list2 = list(stat.items())
list2.sort(key = lambda x:x[1],reverse = True)

print(“{} {}”.format(list2[-1][0],list2[0][0]))




#define x first
#define y second

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        if(mat.empty() || mat[0].empty()) return mat;
        int row = mat.size(), col = mat[0].size();
        vector<vector<int>> dist(row, vector<int>(col, -1));
        typedef pair<int, int> PII;
        queue<PII> q;

        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                if(mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while(q.size()) {
            PII cur = q.front();
            q.pop();
            for(int i = 0; i < 4; i ++) {
                int x = cur.x + direction[i][0];
                int y = cur.y + direction[i][1];
                if(x >= 0 && x < row && y >= 0 && y < col && dist[x][y] == -1) {
                    dist[x][y] = dist[cur.x][cur.y] + 1;
                    q.push({x, y});
                }
            }
        }
        return dist;
    }
};



A

答案: $2048$

进制转换

将 $2022$ 转化为二进制为 $11111100110$ ,取比其多一位的二进制数只有最高位为 $1$,即 $100000000000$ ,转化为十进制就是 $2048$ (进制转换的代码应该熟记于心的啊)

C++ 代码

//p进制(2~36)转为十进制 
int p_to_ten(char s[], int p)
{
    //s[]为顺序存储的p进制字符串 
    int x = 0;
    for (int i = 0; s[i]; i++)
    {
        x *= p;
        if (s[i] >= 'A' && s[i] <= 'Z') x += (s[i] - 'A' + 10);
        else x += (s[i] - '0');
    }
    return x;
}

char s[];
int len;
//十进制转为p进制 
void ten_to_p(int x, int p)
{
    int tmp = 0;
    do{
        tmp = x % p;
        if (tmp < 10) s[len++] = '0' + tmp;
        else s[len++] = 'A' + tmp - 10;
        x /= p;
    }while(x);
    //s[]中从len-1到0倒序存储 
}

B

答案: $26390$

模拟,日期处理

C++ 代码

int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int y) //判断闰年 
{
    return (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0));
}

int cnt(int y, int m, int d)
{
    int ans = d;
    for (int i = 1949; i < y; i++) //加年 
    {
        if (check(i)) ans += 366;
        else ans += 365;
    }
    for (int i = 0; i < m; i++) //加月 
    {
        ans += mon[i];
    }
    if (m > 2 && check(y)) ans++;
    return ans;
}

void solve()
{
    cout << cnt(2022, 1, 1) - cnt(1949, 10, 1) << endl;
}

C

答案: $1038$

也是进制转换

C++ 代码

int p_to_ten(string s, int p)
{
    int x = 0;
    for (int i = 0; i < s.size(); i++)
    {
        x *= p;
        if (s[i] >= 'A' && s[i] <= 'Z') x += (s[i] - 'A' + 10);
        else x += (s[i] - '0');
    }
    return x;
}

bool check(int x)
{
    int y = p_to_ten(to_string(x), 16);
    return y % x == 0;
}

void solve()
{
    for (int i = 10; ; i++)
    {
        if (check(i)) 
        {
            cout << i << endl;
            break;
        }
    }
}

D

答案: $592$

线性DP

基础的线性DP问题,参考摘花生那道题,至于说题目的那个怎么读入,可以复制进一个txt文件,然后读取txt文件。
用 $a[i][j]$ 表示第 $i$ 行第 $j$ 列的数值, $f[i][j]$ 表示走到第 $i$ 行 第 $j$ 列时数字和的最大值,则能够得到状态方程为
$f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j]$

C++ 代码

const int N = 65;
char s[N][N];
int f[N][N];

void solve()
{
    ifstream cin("4.in");
    
    for (int i = 1; i <= 30; i++) cin >> s[i] + 1;
    
    for (int i = 1; i <= 30; i++)
        for (int j = 1; j <= 60; j++)
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + (s[i][j] - '0');
        
    cout << f[30][60] << endl;
}

E

答案: $33$

01背包问题变形

把1到2022所有素数都筛出来,这里是填空题,随便怎么筛都可以,最后筛出来306个素数,至于筛素数,这里如果不会的话就试除法筛就可以,然后就是01背包求最大物品数量,这里就不把闫氏DP分析法写一遍了

C++ 代码

const int N = 2030;
bool st[N];
int v[N], f[N][N];
vector<int> prime;
int cnt;

void solve()
{
    getPrime(2022); //筛素数 
    for (auto& c : prime)
    {
        v[++cnt] = c;
    }

    for (int i = 1; i <= 306; i++)
        for (int j = 2022; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + 1);

    cout << f[2022] << endl;
}

F

模拟

C++ 代码

typedef long long LL;
LL t, c, s;
void solve()
{
    cin >> t >> c >> s;
    cout << (s - c) * t / c;
}

G

集合判重

C++ 代码

const int N = 110;
unordered_set<string> st;
int n;
string s[N];

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
    }
    
    for (int i = 1; i <= n; i++) 
    {
        if (!st.count(s[i])) cout << s[i] << endl;
        st.insert(s[i]);
    }
}

H

双指针

枚举原串中最长的回文后缀,将此时的前缀翻转后接在原字符串后即可,但注意前缀可能为空

C++ 代码

bool check(string s)
{
    int i = 0, j = s.size() - 1;
    while (i < j)
    {
        if (s[i] != s[j]) return false;
        i++, j--;
    }
    return true;
}

void solve()
{
    cin >> s;
    int n = s.size();
    for (int i = 0, j = n; i < n; i++, j--)
    {
        string temp = s.substr(i, j);
        if (check(temp))
        {
            string s1 = s.substr(0, i);
            string s2 = s1;
            if (s1.size())
            {
                reverse(s2.begin(), s2.end());
                cout << s1 + temp + s2 << endl;
            }
            else cout << temp << endl;
        }
    }
}

I

搜索(如果数据量更大就需要用上前缀和)

搜索的起始点可以直接去掉最外圈,只搜2~n-1行的2~m-1列,至于后面那个函数叫dfs(实际跟dfs没关系)只是函数写顺手了,有点像深搜的思路,要注意的是四个方向都搜到了和中心相同字母才算是一个’X’

C++ 代码

typedef pair<int,int> PII;

const int N = 110;
int n, m;
char p[N][N];
int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};

bool check(int x, int y)
{
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

bool bfs(int x, int y, char c, int s)
{
    int cnt = 0;
    for (int i = 0; i < 4; i++)
    {
        int xt = x + s * dx[i], yt = y + s * dy[i];
        if (check(xt, yt))
        {
            if (p[xt][yt] != c) return false;
            cnt++;
        } 
    }
    if (cnt == 4) return true;
    else return false;
}

int dfs(int x, int y)
{
    int s = 1;
    while (bfs(x, y, p[x][y], s)) s++;
    return s - 1;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i] + 1;
    }
    int ans = 0;
    for (int i = 2; i <= n - 1 ; i++)
    {
        for (int j = 2; j <= m - 1; j++)
        {
            ans += dfs(i, j);
        }
    }
    cout << ans << endl;
}

J

树状数组/归并排序/线段树

这里就给出树状数组的解法。
考虑每个后缀中的第一个元素应该被交换几次才能满足升序,第一种情况就是已经升序,不需要交换,第二种情况就是后面小于其的数都要与其交换。从前往后枚举每一个后缀,就可以计算出逆序对的数量。树状数组可以在 $O(n log 2k)$ 的时间复杂度求出逆序对的数量(其中k为数组中最大值与最小值的差值),在本题中比$O(n log n)$的归并排序要快,记得要来long long,至于我的代码中为什么没有写成long long,是因为我写了这行代码:

#define int long long

但此时注意一下,main函数的返回值必须是int,main函数这样改写就可以了

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*......*/
    return 0;
}

适合不确定是否开long long的情况下。
有必要提醒一下,在数据量比较大的情况下,cin和cout会很慢,会部分数据导致超时,如果不愿意写scanf和printf的可以在main函数前面开头加上上面那几行代码,但加上后就不要再使用scanf和printf。

C++ 代码

const int N = 1e6 + 10;
int n, a[N], tr[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i)) 
    {
        tr[i] += c;
    }
}

int sum(int x)
{
    int ans = 0;
    for (int i = x; i; i -= lowbit(i)) 
    {
        ans += tr[i];
    }
    return ans;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    
    int ans = 0;
    for (int i = n; i; i--)
    {
        ans += sum(a[i] - 1) * a[i];
        add(a[i], 1);
    }
    cout << ans << endl;
}



截屏2022-12-09 00.34.55.png

代码

Java 自带快速排序

import java.util.*;
import java.io.*;

public class Main {
    static int N = 100010, NaN = 0x3f3f3f3f, n;

    /**
     * 自定义数据类型,实现 Comparable 借口,方便 Arrays.sort 排序
     */  
    static class Edge implements Comparable<Edge> {
        int a;
        int b;
        int w;
        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
        @Override
        public int compareTo(Edge e) {
            return w - e.w;
        }
    }

    /**
     * 点边关系数组,不能有 null ,会影响排序
     */ 
    static Edge[] es;

    /**
     * 并查集数组
     */ 
    static int[] p = new int[N];

    /**
     * 查询某个节点的集合根节点编号
     */ 
    static int find(int i) {
        if (p[i] != i) p[i] = find(p[i]);
        return p[i];
    }

    /**
     * Kruskal 算法
     */ 
    static int kruskal() {
        // 将点边关系数组,从小到大排序
        Arrays.sort(es);
        // res 最小生成树边权之和,cnt 构成最小生成树的边数之和
        int res = 0, cnt = 0;
        // 遍历每条边
        for (Edge e : es) {
            // 查询两点所属集合的根节点编号
            int pa = find(e.a);
            int pb = find(e.b);
            // 如果两点未连通
            if (pa != pb) {
                // 连通两点
                p[pa] = pb;
                // 边权值之和,加上当前边的权值
                res += e.w;
                // 边数 + 1
                cnt ++;
            }
        }
        // 遍历完每条边之后,如果生成的最小生成树边数,比总点数 - 1 小,说明有未连通的点,不存在最小生成树
        // 否则返回最小生成树的边权之和
        return cnt < n - 1 ? NaN : res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        n = sc.nextInt();
        // 初始将所有点默认不连通,分属单独的集合
        for (int i = 1; i <= n; i ++) {
            p[i] = i;
        }
        int m = sc.nextInt();
        es = new Edge[m];
        for (int i = 0; i < m; i ++) {
            es[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }
        int t = kruskal();
        System.out.println(t == NaN ? "impossible" : t);
        sc.close();
    }
}

手写快速排序

import java.util.*;
import java.io.*;

public class Main {

    static int N = 100010, NaN = 0x3f3f3f3f, n, m;

    /**
     * 自定义数据类型,存储点边关系
     */  
    static class Edge {
        int a, b, w;
        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }

    /**
     * 点边关系数组
     */ 
    static Edge[] es;

    /**
     * 并查集数组
     */ 
    static int[] p = new int[N];

    /**
     * 查询某个节点的集合根节点编号
     */ 
    static int find(int i) {
        if (p[i] != i) p[i] = find(p[i]);
        return p[i];
    }

    /**
     * 手写快速排序
     */ 
    static void quickSort(int l, int r) {
        if (l >= r) return;
        Edge ed = es[l];
        int i = l - 1, j = r + 1;
        while (i < j) {
            do i ++; while (es[i].w < ed.w);
            do j --; while (es[j].w > ed.w);
            if (i < j) {
                Edge t = es[i];
                es[i] = es[j];
                es[j] = t;
            }
        }
        quickSort(l, j);
        quickSort(j + 1, r);
    }

    /**
     * kruskal 算法
     */ 
    static int kruskal() {
        // 将点边关系数组,从小到大排序
        quickSort(0, m - 1);
        // res 最小生成树边权之和,cnt 构成最小生成树的边数之和
        int res = 0, cnt = 0;
        // 遍历每条边
        for (Edge e : es) {
            // 查询两点所属集合的根节点编号
            int pa = find(e.a), pb = find(e.b);
            // 如果两点未连通
            if (pa != pb) {
                // 连通两点
                p[pa] = pb;
                // 边权值之和,加上当前边的权值
                res += e.w;
                // 边数 + 1
                cnt ++;
            }
        }
        // 遍历完每条边之后,如果生成的最小生成树边数,比总点数 - 1 小,说明有未连通的点,不存在最小生成树
        // 否则返回最小生成树的边权之和
        return cnt < n - 1 ? NaN : res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        n = sc.nextInt();
        // 初始将所有点默认不连通,分属单独的集合
        for (int i = 1; i <= n; i ++) {
            p[i] = i;
        }
        m = sc.nextInt();
        es = new Edge[m];
        for (int i = 0; i < m; i ++) {
            es[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }
        int t = kruskal();
        System.out.println(t == NaN ? "impossible" : t);
        sc.close();
    }
}



class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size();
        for(int i = 0; i < n; i += 2 * k) {
            reverse(s.begin() + i, s.begin() + min(n, i + k));
        }
        return s;
    }
};