A 三连-签到！
using namespace std;
using i64 = long long;
#define all(t) t.begin(), t.end()
void solve()
{
int n; cin >> n;
int ans = 0;
map<int,int> cnt;
for (int i = 0;i < n;i ++)
{
int x;cin >> x;
cnt[x] ++;
}
for (auto [k, v] : cnt)
{
ans += v / 3;
}
cout << ans;
}
signed main()
{
std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
int _ = 1;// std::cin >> _;
while (_ --) solve();
return 0;
}
B 会长的牌子呢？
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m;
string s;
void solve()
{
int x1, x2, x3, y1, y2, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
int xx1 = x2 - x1, yy1 = y2 - y1, xx2 = x3 - x1, yy2 = y3 - y1;
cout << fixed << setprecision(1) << abs(1.0 * (xx1 * yy2 - xx2 * yy1)) / 2;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
C 走迷宫
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define all(t) t.begin(), t.end()
using PII = pair<int, int>;
const int INF = 0x3f3f3f3f;
void solve()
{
int n, m; cin >> n >> m;
vector<string> s(n + 1);
vector<vector<int>> dis(n + 1, vector<int> (m + 1, 0x3f3f3f3f));
for (int i = 1;i <= n;i ++)
{
cin >> s[i];
s[i] = ' ' + s[i];
}
PII S, T;
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++)
{
if (s[i][j] == 'S') S = {i, j};
if (s[i][j] == 'E') T = {i, j};
}
dis[S.first][S.second] = 0;
queue<PII> q;
q.push(S);
while (q.size())
{
auto [x, y] = q.front();
q.pop();
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
for (int i = 0;i < 4;i ++)
{
int tx = x + dx[i], ty = y + dy[i];
if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
if (s[tx][ty] == '@') continue;
if (dis[tx][ty] != INF) continue;
dis[tx][ty] = dis[x][y] + 1;
q.push({tx, ty});
}
}
cout << (dis[T.first][T.second] == INF ? -1 : dis[T.first][T.second]);
}
signed main()
{
//std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
int _ = 1;// std::cin >> _;
while (_ --) solve();
return 0;
}
D 顺时针的正方形
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m;
string s[1005];
void solve()
{
cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i++)
cin >> s[i], s[i] = ' ' + s[i];
for (int i = 1; i <= n / 2; i++)
{
for (int k = 1; k <= n / 2; k++)
{
int x1 = i, y1 = k;
int x2 = k, y2 = n - i + 1;
int x3 = n - i + 1, y3 = n - k + 1;
int x4 = n - k + 1, y4 = i;
int mxch = max(s[x1][y1], max(s[x2][y2], max(s[x3][y3], s[x4][y4])));
ans += mxch * 4 - s[x1][y1] - s[x2][y2] - s[x3][y3] - s[x4][y4];
}
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// tt=1;
cin >> tt;
while (tt--)
solve();
}
E 据说XCPC每题首杀的气球不一样哦
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m, t1[200005], t2[200005];
string s;
bool ck(int t)
{
int sm = 0;
for (int i = 1; i <= n; i++)
{
int ns = t / (t1[i] + t2[i]);
if (t - ns * (t1[i] + t2[i]) >= t1[i])
ns++;
sm += ns;
}
return sm >= m;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> t1[i] >> t2[i];
}
int l = 0, r = mod, mid, ans = mod;
while (l <= r)
{
mid = l + r >> 1;
if (ck(mid))
ans = mid, r = mid - 1;
else
l = mid + 1;
}
cout << ans;
/*int sm=0;
for(int i=1;i<=n;i++){
int ns=ans/(t1[i]+t2[i]);
if(ans-ns*(t1[i]+t2[i])>=t1[i])ns++;
cout<<ns<<' ';sm+=ns;
}
cout<<sm;*/
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
F 最大子区间
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m, a[200005], b[200005];
string s;
void solve()
{
cin >> n >> m;
int mx = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = b[i - 1] + a[i] - a[max(0, i - m)];
if (b[i] > mx)
{
mx = b[i];
}
}
// for (int i = 1; i <= 100; i++)cout << b[i] << ' ';
// cout << '\n';
// cout<<mx<<'\n';
for (int i = 1; i <= n; i++)
{
if (b[i] == mx)
{
int r = i, l = max(1, i - m + 1);
cout << l << ' ' << r << '\n';
while (a[l] == 0 && l + 1 <= r)
{
cout << ++l << ' ' << r << '\n';
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
G 最大最长子区间
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m, a[200005], dp[200005], l[200005];
string s;
vector<pair<int, int>> vt;
void solve()
{
cin >> n;
int mx = 0, mx_len = 0;
l[0] = 1;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (dp[i - 1] + a[i] >= 0)
{
dp[i] = dp[i - 1] + a[i];
l[i] = l[i - 1];
}
else
{
dp[i] = 0;
l[i] = i + 1;
}
mx = max(mx, dp[i]);
}
// for(int i=1;i<=n;i++)cout<<dp[i]<<' ';cout<<'\n';
// for(int i=1;i<=n;i++)cout<<l[i]<<' ';cout<<'\n';
for (int i = 1; i <= n; i++)
{
if (dp[i] == mx)
{
int len = i - l[i] + 1;
if (len > mx_len)
{
vt.clear();
mx_len = len;
}
if (mx_len == len)
vt.push_back({l[i], i});
}
}
for (auto it : vt)
cout << it.first << ' ' << it.second << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
H 团建前的准备
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m;
string s;
map<int, map<int, int>> mp;
set<int> st[200005];
priority_queue<pair<int, int>> q;
priority_queue<pair<double, int>> q2;
void solve()
{
cin >> n >> m;
int x, y, z;
for (int i = 1; i <= m; i++)
{
cin >> x >> y >> z;
mp[x][y] = max(mp[x][y], z);
st[x].insert(y);
}
for (int i = 1; i <= n; i++)
{
int w = 0;
for (auto it : st[i])
w += mp[i][it];
q.push({w, i});
if (w)
q2.push({1.0 * w / st[i].size(), i});
}
cout << q.top().second << ' '; // 总评分最高
cout << q2.top().second << '\n'; // 防止踩雷
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
I 赶不上团建啦
这里我用的是深搜回去找状态的方法
因为一开始是想把每条最短路径详细输出的
后来还是降低了点难度
不过没人在比赛的时候做出来
也许不该减的？
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m, dis[200005], ans, cnt, lu[200005];
string s;
struct node
{
int v, w;
};
vector<node> vt[200005];
set<int> e[200005];
queue<int> q;
void dfs(int u)
{
if (u == 1)
{
// for(int i=cnt;i;i--)cout<<lu[i]<<' ';cout<<'\n';
ans++;
return;
}
for (auto it : e[u])
{
lu[++cnt] = it;
dfs(it);
cnt--;
}
}
void solve()
{
cin >> n >> m;
int u, v, w;
memset(dis, 0x7f, sizeof(dis));
dis[1] = 0;
for (int i = 1; i <= m; i++)
{
cin >> u >> v >> w;
vt[u].push_back({v, w});
vt[v].push_back({u, w});
}
q.push(1);
while (!q.empty())
{
int u = q.front();
q.pop();
for (auto it : vt[u])
{
int v = it.v, w = it.w + dis[u];
if (w < dis[v])
{
dis[v] = w;
q.push(v);
e[v].clear();
e[v].insert(u);
}
else if (w == dis[v])
{
e[v].insert(u);
}
}
}
if (dis[n] == int(0x7f7f7f7f))
cout << "-1\n";
else
cout << dis[n] << '\n';
lu[++cnt] = n;
dfs(n);
cout << ans << '\n';
// for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
J 终于团建上了
这个题本意是想让挑战者用线段树做的，但其实通过前缀差分的方法也可以
不过数据当时没捏好，有人偷偷蒙混过关了！现在数据已修正
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m, a[150000], k; // 10Ěě144000ˇÖÖÓ
int lowbit(int x)
{
return x & -x;
}
void add(int id, int x)
{
for (int i = id; i <= 144000; i += lowbit(i))
a[i] += x;
}
int tk(int id)
{
int ans = 0;
for (int i = id; i; i -= lowbit(i))
ans += a[i];
return ans;
}
void solve()
{
cin >> n >> m >> k;
int id, l, r;
for (int i = 1; i <= k; i++)
{
cin >> id >> l >> r;
add(l, 1);
add(r + 1, -1);
// for(int i=1;i<=10;i++)cout<<tk(i)<<' ';cout<<'\n';
}
for (int i = 1; i <= 144000; i++)
{
if (n <= m - tk(i))
{
cout << i;
return;
}
}
cout << "-1";
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
K 最简数
应该是很简单的一个模拟
每次压缩一下再回退一下就ok了
再考虑“22”的情况，会不会一直陷入死循环
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m, a[200005], b[200005];
string s;
void solve()
{
cin >> n >> s;
for (int i = 0; i < n; i++)
{
int ns = 1;
while (i < n - 1 && s[i] == s[i + 1])
i++, ns++;
if (ns == 1)
{
continue;
}
if (ns == 2 && s[i] == '2')
continue;
string sr = s[i] + to_string(ns);
n = n - (ns - sr.size());
i = i - ns;
s.replace(i + 1, ns, sr);
// cout<<s<<'\n';
}
cout << s;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
tt = 1;
// cin>>tt;
while (tt--)
solve();
}
但是每次通过replace()操作时间复杂度最坏为O(n^2),在数据足够强的话也会被卡掉
加上很多人喜欢在for(int i=0;i<s.size();i++)里面使用replace()，去看看c++的书，想想为什么不能这么干
下面是O(n)的做法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
int tt,n,m,ns;
string s,ss;
void solve(){
cin>>n>>s;
for(int i=0;i<n;i++){
if(i==n-1||s[i]!=s[i+1]){cout<<s[i];continue;}//
ns=1;
while(s[i]==s[i+1])i++,ns++;
ss=s[i]+to_string(ns);
if(ss=="22"){cout<<"22";continue;}
for(int k=ss.size()-1;k>=0;k--,i--)s[i]=ss[k];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
//cin>>tt;
tt=1;
while(tt--)solve();
return 0;
}
L 梦不可及的ak
这个题就非常有意思了
总体考虑三种情况，答案分别为n,2~n-1,1
其中n的情况只有在所有数字相同的情况下得到
1的话是万能答案，但是我们求得是最大值，答案可能不是1
那么我们在排除n的情况下，只需要考虑2~n-1的情况，最后无脑输出1即可
我们从答案出发，假设n个数不断选取m个数-1，剩下的数都为x，一共选取了y次，可以发现x*n+y*m=sm,其中sm为原数组的总和
限制条件为 0<=x<=mi(mi为原数组的最小值),y>=0(非负即可)
但是二元一次方程(exgcd)似乎有点难记，所以我在比赛要求后面加上可以带纸质资料，不过思维关不知道有没有人过掉。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int tt, n, m, a[200005];
string s;
void exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
void solve()
{
cin >> n;
int mi = mod, sm = 0, mx = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
mi = min(mi, a[i]);
mx = max(mx, a[i]);
sm = sm + a[i];
}
if (mi == mx)
{
cout << n << '\n';
return;
}
for (int i = n - 1; i > 1; i--)
{
ll x, y, aa = n, bb = i, c = sm, gd = __gcd(aa, bb);
if (sm % gd != 0)
continue;
aa /= gd;
bb /= gd;
c /= gd;
exgcd(aa, bb, x, y);
ll xx = x * sm, yy = y * sm;
int ns = xx / bb;
xx -= ns * bb, yy += ns * aa;
if (x < 0)
xx += bb, yy -= aa;
if (xx > mi || yy < 0)
continue;
cout << i << '\n';
return;
}
cout << "1\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// tt=1;
cin >> tt;
while (tt--)
solve();
}
京公网安备 11010502036488号