A - Pairing
题意
给\(4\)个数，每次选两个数字相同的丢掉。求最大操作数。
思路
模拟。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve()
{
int a, b, c, d;
cin >> a >> b >> c >> d;
map<int, int> m;
m[a]++;
m[d]++;
m[c]++;
m[b]++;
int ans = 0;
for (auto& i : m)
{
ans += i.second / 2;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
B - Garbage Collection
题意
有\(n\)种垃圾，对于第\(i\)种垃圾，当日期对\(q_i\)取模等于\(r_i\)时，这种垃圾会被回收。有\(Q\)次查询，对于第\(j\)次查询，给定垃圾类型\(t_j\)和投放日期\(d_j\)，输出这种垃圾下一次被回收的日期。
注：如果垃圾的投放日期和收集日期相同，则垃圾会在当天被回收。
思路
模拟。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
void solve()
{
int n;
cin >> n;
vector<int> q(n), r(n);
for (int i = 0; i < n; ++i)
{
cin >> q[i] >> r[i];
}
int Q;
cin >> Q;
while (Q--)
{
int t, d;
cin >> t >> d;
t--;
int qi = q[t], ri = r[t];
int now = d % qi, ans;
if (now == ri)
{
ans = d;
}
else if (now < ri)
{
ans = d + ri - now;
}
else
{
ans = d + qi - now + ri;
}
cout << ans << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
C - Repeating
题意
给定长度为\(n\)的正整数序列\(A\ =\ (A_1,A_2,···,A_n)\)。定义序列\(B\ =\ (B_1,B_2,···，B_n)\)，对于\(i\ =\ 1,2,···,n\)，若存在\(j\ (j < i)\)使得$$A_i=A_j\(则\)B_i = j\(，否则\)B_i = -1$。
思路
模拟，怕超时用了个\(set\)记录下标到\(i\)时出现过的元素。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
void solve()
{
int n;
cin >> n;
vector<int> v(n), b(n, -1);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
set<int> s;
for (int i = 0; i < n; i++)
{
if (s.count(v[i]))
{
for (int j = i - 1; j >= 0; j--)
{
if (v[j] == v[i])
{
b[i] = j + 1;
break;
}
}
}
s.insert(v[i]);
}
for (int i = 0; i < n; i++)
{
cout << b[i] << " ";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
D - Count Simple Paths
题意
给定\(h\)行、\(w\)列的图，"."表示空，"#"表示阻塞。求从每个点出发，不被阻塞的、长度为\(k+1\)的路径条数(不能重复经过一点)。
思路
数据非常小，直接搜。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 15;
char mp[mxn][mxn];
bool vis[mxn][mxn];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int h, w, k;
int ans;
void dfs(int x, int y, int step)
{
if (step == k)
{
ans++;
return;
}
for (int i = 0; i < 4; i++)
{
int tx = x + dx[i];
int ty = y + dy[i];
if (tx < 0 || tx >= h || ty < 0 || ty >= w || vis[tx][ty] || mp[tx][ty] == '#')
{
continue;
}
vis[tx][ty] = true;
dfs(tx, ty, step + 1);
vis[tx][ty] = false;
}
}
void solve()
{
cin >> h >> w >> k;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
cin >> mp[i][j];
}
}
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (mp[i][j] == '.')
{
vis[i][j] = true;
dfs(i, j, 0);
vis[i][j] = false;
}
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
E - Mod Sigma Problem
题意
给定\(n\)、\(m\)，求：
思路
代码
点击查看代码