1
#include <bits/stdc++.h>
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define x first
#define y second
using namespace std;
const int N = 1e4 + 10;
int n, k;
void solve()
{
cin >> n >> k;
// if((n - 1) % (k - 1) == 0) cout << (n - 1)/(k - 1);
// else cout << (n - 1) / (k - 1) + 1;
cout << (n + k - 2) / (k - 1);
}
int main()
{
IOS
// freopen("1.in", "r", stdin);
// cin >> t;
solve();
return 0;
}
2
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
queue<string>q;
char c[100];
int n;
void solve()
{
scanf("%d", &n);
while(n --)
{
cin >> (c + 1);
//如果当前是in的话我们就让这个同学入队
if(c[1] == 'i')
{
string name;
cin >> name;
q.push(name);
}
//如果，当前是out，我们就将队头元素出队
else if(c[1] == 'o') q.pop();
//如果当前是q的话，我们就查询队头元素，题目中的样例给的也提示我们队空这种情况
else
{
if(q.size() == 0) cout << "NULL" << endl;
else
{
string t = q.front();
cout << t << endl;
}
}
}
}
int main()
{
// freopen("1.in", "r", stdin);
solve();
return 0;
}
3
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 10;
char a[N];
// path数组用于记录我们枚举的排列，st用来标记每个数是否用过
int path[N], st[N];
int n;
//u是我们枚举到那个位置了
void dfs(int u)
{
//当我们枚举完所有的n个位置的数这时候我们就找到了一种排列
if(u == n )
{
for(int i = 0; i < n; i ++) cout << a[path[i]];
puts("");
}
//枚举第u个位置应该是那个数
for(int i = 0; i < n; i ++)
{
//如果这个数已经用过了，我们直接continue
if(st[i]) continue;
//如果没有用过，我们就在当前位置放这个数，并且标记这个数已经用过（排列中一个数只能用一次）
path[u] = i;
st[i] = 1;
//递归到下一层
dfs(u + 1);
//记得回溯，因为我们当前这个位置还需要去枚举放其他数字的情况
st[i] = 0;
}
}
int main()
{
scanf("%s", a);
for(int i = 0; a[i]; i ++) n ++;
//这里我们预处理一下之前的字符串数组，让字符串内部本身就是按字典序排列的
sort(a, a + n);
//开始枚举
dfs(0);
return 0;
}
4
#include <bits/stdc++.h>
#define LL long long
using namespace std;
using ll = long long;
const int N = 1e4 + 10;
int m, n;
void solve()
{
map<int, int>s1, s2;
set<int>ans1, ans2;
cin >> n >> m;
for(int i = 1; i <= n; ++ i)
{
int x; cin >> x;
s1[x] ++;
}
for(int i = 1; i <= m; ++ i)
{
int x; cin >> x;
s2[x] ++;
}
for(auto x:s1)
{
ans2.insert(x.first);
if(s2.find(x.first) != s2.end()) ans1.insert(x.first);
}
for(auto x:s2) ans2.insert(x.first);
cout << ans1.size();
if(ans1.size() != 0) cout << ' ';
int cnt1 = 0;
for(auto x : ans1)
{
cout << x;
if(cnt1 != ans1.size() - 1) cout << ' ';
++ cnt1;
}
cout << endl;
cout << ans2.size();
if(ans2.size() != 0) cout << ' ';
int cnt2 = 0;
for(auto x : ans2)
{
cout << x;
if(cnt2 != ans2.size() - 1) cout << ' ';
++ cnt2;
}
cout << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
// cin >> t;
solve();
return 0;
}
5
#include <bits/stdc++.h>
#define LL long long
using namespace std;
using ll = long long;
const int N = 1e4 + 10;
int t, n;
void solve()
{
map<string, int>mp;
cin >> n;
for(int i = 1; i <= n; ++ i)
{
string str; cin >> str;
mp[str] ++;
}
for(auto x : mp) cout << x.first << ' ' << x.second << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
cin >> t;
while(t --) solve();
return 0;
}
6
#include <bits/stdc++.h>
#define LL long long
using namespace std;
using ll = long long;
const int N = 1e4 + 10;
int n, t;
void solve()
{
stack<char>stk;
string s; cin >> s;
for(int i = 0; i < s.size(); ++ i)
{
if(s[i] == '{' || s[i] == '(' || s[i] == '[') stk.push(s[i]);
else
{
if(stk.size() == 0)
{
puts("No");
return;
}
if(s[i] == '}' && stk.top() == '{') stk.pop();
else if(s[i] == ')' && stk.top() == '(') stk.pop();
else if(s[i] == ']' && stk.top() == '[') stk.pop();
else
{
puts("No");
return;
}
}
}
if(stk.size() != 0) puts("No");
else puts("Yes");
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
cin >> t;
while(t --) solve();
return 0;
}
7
#include <bits/stdc++.h>
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define x first
#define y second
using namespace std;
const int N = 1e4 + 10;
int n, k;
string a, b;
void solve(string a, string b)
{
if(!a.size() || !b.size()) return;
char ch = a[a.size() - 1];
cout << ch;
int idx = b.find(ch);
solve(a.substr(0, idx), b.substr(0, idx));
solve(a.substr(idx, a.size() - idx - 1), b.substr(idx + 1));
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
cin >> n;
cin >> a >> b;
solve(a, b);
return 0;
}
8
#include <bits/stdc++.h>
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define x first
#define y second
using namespace std;
const int N = 1e4 + 10;
int n, k;
void solve()
{
priority_queue<int, vector<int>, greater<int> >pq;
cin >> n >> k;
for(int i = 1; i <= n; ++ i)
{
int x; cin >> x;
pq.push(x);
}
for(int i = 1; i <= k; ++ i)
{
if(i == k) cout << pq.top();
pq.pop();
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
solve();
return 0;
}
9
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
int q[N], tmp[N];
int n;
LL merge_sort(int l, int r)
{
//当区间中只有一个数时，逆序对的数量为0
if(l >= r) return 0;
int mid = (l + r) >> 1;
//递归求解两边的逆序对数量
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
//求解第三类逆序对数量
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k ++] = q[i ++];
else
{
tmp[k ++ ] = q[j ++];
res += mid - i + 1;
}
}
while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++ ] = q[j ++];
for(int i = l, j = 0; i <= r; ++ i, ++ j) q[i] = tmp[j];
return res;
}
int main()
{
cin >> n;
for(int i = 0; i < n; ++ i) cin >> q[i];
cout << merge_sort(0, n - 1) << endl;
return 0;
}