#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;
}
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();
}
}
s1 = input()
s2 = input()
s3 = input()
for word in s1.split(" "):
if word == s2:
print(s3, end=' ')
else:
print(word, end=' ')
#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;
}
#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;
}
#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;
}
str_list = input().split(' ')
for i in range(len(str_list)-1, -1, -1):
print(str_list[i], end=' ')
房间里放着 $n$ 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 $(0,0)$ 点处。
第一行有一个整数，表示奶酪的数量 $n$。
第 $2$ 到第 $(n + 1)$ 行，每行两个实数，第 $(i + 1)$ 行的实数分别表示第 $i$ 块奶酪的横纵坐标 $x_i, y_i$。
输出一行一个实数，表示要跑的最少距离，保留 $2$ 位小数。
4
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}$ 数据。
切记状态要记录齐，必须记录当前位置和已经走过的位置，不能忽略任何一个，否则就是逻辑漏洞
#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方法
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;
}
};
答案： $2048$
将 $2022$ 转化为二进制为 $11111100110$ ，取比其多一位的二进制数只有最高位为 $1$，即 $100000000000$ ，转化为十进制就是 $2048$ （进制转换的代码应该熟记于心的啊）
//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倒序存储
}
答案： $26390$
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;
}
答案： $1038$
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;
}
}
}
答案： $592$
基础的线性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]$
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;
}
答案： $33$
把1到2022所有素数都筛出来，这里是填空题，随便怎么筛都可以，最后筛出来306个素数，至于筛素数，这里如果不会的话就试除法筛就可以，然后就是01背包求最大物品数量,这里就不把闫氏DP分析法写一遍了
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;
}
typedef long long LL;
LL t, c, s;
void solve()
{
cin >> t >> c >> s;
cout << (s - c) * t / 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]);
}
}
枚举原串中最长的回文后缀，将此时的前缀翻转后接在原字符串后即可，但注意前缀可能为空
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;
}
}
}
搜索的起始点可以直接去掉最外圈，只搜2~n-1行的2~m-1列，至于后面那个函数叫dfs(实际跟dfs没关系)只是函数写顺手了，有点像深搜的思路，要注意的是四个方向都搜到了和中心相同字母才算是一个’X’
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;
}
这里就给出树状数组的解法。
考虑每个后缀中的第一个元素应该被交换几次才能满足升序，第一种情况就是已经升序，不需要交换，第二种情况就是后面小于其的数都要与其交换。从前往后枚举每一个后缀，就可以计算出逆序对的数量。树状数组可以在 $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。
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;
}
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;
}
};
