A题
题目要求为给出一串数,要求查询这一串数中的每个数,但需要"字典",字典根据已查询的数来制定,即正在查询的数未在字典中就添加,但字典有最大容量,在字典中未找到查询数就计数,问计数量.
思路为:开一数组,记录字典,每次字典超上限就改变查询数组的开始与结束.代码如下:
#include<bits/stdc++.h>
using i64 = long long;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n , m;
std::cin >> n >> m;
std::vector<int> ma(m + 1 , -1);
int sum = 0;
for(int i = 0;i < m;i++)
{
int a;
bool tr = 0;
std::cin>> a;
for(int j = std::max(sum - n + 1 , 1);j <= std::max(sum , n);j++)
{
if(ma[j] == a)
{
tr = 1;
break;
}
}
if(tr)
continue;
else
{
sum++;
ma[sum] = a;
}
}
std::cout<< sum << "\n";
return 0;
}B题
题目为给出一定数量的城市和州名,要求找出与之相对的城市和州.
思路是题解区一个大佬的,没用map,将城市名和州名转换为具体数值,借由二维数组来确定有多少个相对应的地方.代码如下:
#include<bits/stdc++.h>
using i64 = long long;
int ma[676][676];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin>> n;
int sum = 0;
std::string a , b;
while(n--)
{
std::cin>> a >> b;
int x = (a[0] - 'A') * 26 + a[1] - 'A';
int y = (b[0] - 'A') * 26 + b[1] - 'A';
if(x != y)
{
ma[x][y]++;
sum += ma[y][x];
}
}
std::cout<< sum << "\n";
return 0;
}C题
题目要求为给数组排序,并给出过程.
思路是直接两次冒泡排序,一次记录次数,一次输出过程.代码如下:
#include<bits/stdc++.h>
using i64 = long long;
int ma[676][676];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n , m;
std::cin>> m >> n;
std::vector<std::vector<int>> a(n + 1 , std::vector<int>(m + 1)) , b(n + 1 , std::vector<int>(m + 1));
std::vector<double> l(n) , r(n) , c(n);
for(int i = 0;i < n;i++)
{
double la = 0.0;
for(int j = 0;j < m;j++)
{
std::cin>> a[i][j];
la += (double)a[i][j] * 1.0;
}
la /= m * 1.0;
for(int j = 0;j < m;j++)
{
l[i] += (a[i][j] - la) * (a[i][j] - la);
}
c[i] += l[i] / m;
}
for(int i = 0;i < n;i++)
{
double lb = 0;
for(int j = 0;j < m;j++)
{
std::cin>> b[i][j];
lb += (double)b[i][j] * 1.0;
}
lb /= m;
for(int j = 0;j < m;j++)
{
r[i] += (b[i][j] - lb) * (b[i][j] - lb);
}
c[i] += r[i] / m;
}
std::vector<double> d(c);
int ni = 0;
for(int k = 0;k < n;k++)
{
for(int i = 0;i < n - 1;i++)
{
if(d[i] > d[i + 1])
{
double dg = d[i];
d[i] = d[i + 1];
d[i + 1] = dg;
ni++;
}
}
}
std::cout<< ni << "\n";
for(int k = 0;k < n;k++)
{
for(int i = 0;i < n - 1;i++)
{
if(c[i] > c[i + 1])
{
std::cout<< i + 1 << " " << i + 2 << "\n";
double dg = c[i];
c[i] = c[i + 1];
c[i + 1] = dg;
}
}
}
return 0;
}
D题
题目要求为移动数组,给出查询时数组剩余个数.
思路为:记录每次的最大左右移动,每次二分查询出数组的个数,但需特别注意数组大小,本人在这wa了一天......代码如下:
#include<bits/stdc++.h>
using i64 = long long;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n , m;
i64 k;
std::cin>> n >> m>> k;
std::vector<i64> w(n);
for(int i = 0;i < n;i++)
{
std::cin>> w[i];
}
std::sort(w.begin() , w.end());
i64 st = 0;
i64 cl = 0 , cr = 0 , l = 0 , r = n - 1;
while(m--)
{
int dg;
std::cin>> dg;
if(dg == 1)
{
i64 a;
std::cin>> a;
st += a;
}
else if(dg == 2)
{
i64 a;
std::cin>> a;
st -= a;
}
cl = std::min(cl , st);
cr = std::max(cr , st);
while(l <= r && w[l] + cl < -k)
{
l++;
}
while(r >= l && w[r] + cr > k)
{
r--;
}
if(dg == 3)
std::cout<< (r - l + 1) << "\n";
}
return 0;
E题
题目要求:给出三行数组,要求去除一定排后对每行进行排序后得到的结果一样.
思路:因为第一行互不相同(当时昏迷了,死活没想到),就可以直接看2,3行中的缺少的数,直接去掉,然后在看去掉的数里面是否还有没去掉的,如果有就继续.代码如下:
#include<bits/stdc++.h>
using i64 = long long;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin>> n;
std::vector<int> a(n + 2 , 0) , b(n + 2 , 0) , c(n + 2 , 0) , fa(n + 2 , 0) , fb(n + 2 , 0) , fc(n + 2 , 0) , d(n + 1 , 0);
for(int i = 1;i <= n;i++)
{
std::cin>> a[i];
fa[a[i]] = i;
}
for(int i = 1;i <= n;i++)
{
std::cin>> b[i];
fb[b[i]]++;
}
for(int i = 1;i <= n;i++)
{
std::cin>> c[i];
fc[c[i]]++;
}
std::vector<int> v(n + 2 , 0);
std::queue<int> t;
for(int i = 1;i <= n;i++)
{
if(fb[i] == 0 || fc[i] == 0)
t.push(i);
}
int ans = 0;
while(!t.empty())
{
int no = t.front();
t.pop();
int dg = fa[no];
if(v[dg])
continue;
v[dg] = 1;
ans++;
fb[b[dg]]--;
fc[c[dg]]--;
if(fb[b[dg]] == 0)
t.push(b[dg]);
if(fc[c[dg]] == 0)
t.push(c[dg]);
}
std::cout<< ans<< "\n";
return 0;
}F题
题目要求为:给出最大警示天数
思路:先将所有的都按2 x来计算,最后考虑持续时间最长的那些天,对这些天前3 * x到2 * x中的天气进行计算,求得最值.代码如下:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n + 2);
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<pair<int, int>> ice;
for (int i = 1; i <= n; ) {
if (a[i] >= 0) { ++i; continue; }
int j = i;
while (j <= n && a[j] < 0) ++j;
int len = j - i;
ice.emplace_back(i, len);
i = j;
}
if (ice.empty()) {
cout << "0\n";
return 0;
}
int maxT = 0;
for (auto &[s, T] : ice) maxT = max(maxT, T);
vector<int> dif(n + 2, 0);
auto cover = [&](int l, int r) {
if (l > r) return;
l = max(l, 1);
r = min(r, n);
dif[l] += 1;
if (r + 1 <= n) dif[r + 1] -= 1;
};
for (auto &[s, T] : ice) {
int L = s - 2 * T;
int R = s - 1;
cover(L, R);
}
int base = 0;
for (int i = 1, cur = 0; i <= n; ++i) {
cur += dif[i];
if (cur > 0) ++base;
}
int delta = 0;
fill(dif.begin(), dif.end(), 0);
for (auto &[s, T] : ice) {
int L = s - 2 * T;
int R = s - 1;
cover(L, R);
}
for (int i = 1; i <= n; ++i) dif[i] += dif[i - 1];
for (auto &[s, T] : ice) if (T == maxT) {
int L = s - 3 * T;
int R = s - 1;
int gain = 0;
int realL = max(L, 1);
int realR = s - 2 * T - 1;
if (realL <= realR) {
for (int i = realL; i <= realR; ++i)
if (dif[i] == 0) ++gain;
}
delta = max(delta, gain);
}
cout << base + delta << '\n';
return 0;
}G题
题目要求:求每天的最小波动值之和
思路:直接forfor遍历.代码如下:
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin>> n;
std::vector<int> a(n , 1000007);
i64 sum = 0;
for(int i = 0;i < n;i++)
{
std::cin>> a[i];
}
sum = a[0];
for(int i = 1;i < n;i++)
{
int dg = 1000007;
for(int j = i - 1;j >= 0;j--)
{
dg = std::min(dg , std::abs(a[i] - a[j]));
}
sum += dg;
}
std::cout << sum << "\n";
return 0;
}H题
题目要求:去重
思路:因为给出的数太大,1e32,就直接string加哈希表.代码如下:
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
std::cin>> T;
while(T--)
{
int n;
std::cin>> n;
std::unordered_map<std::string , int> shu;
for(int i = 0;i < n;i++)
{
std::string a;
std::cin>> a;
if(shu.find(a) == shu.end())
{
for(int j = 0;j < (int)a.size();j++)
{
if((int)a.size() == 1)
std::cout<< a[j] << " ";
if(j != (int)a.size() && (int)a.size() != 1)
std::cout<< a[j];
if(j == (int)a.size() - 1 && (int)a.size() != 1)
std::cout<< " ";
}
}
shu[a] = i;
}
std::cout<< "\n";
}
return 0;
}I题
题目要求:合并果子
思路:可以想到从最小合并到最大,直接优先队列即可.代码如下:
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin>> n;
std::priority_queue<int , std::vector<int> , std::greater<int>> q;
for(int i = 0;i < n;i++)
{
int a;
std::cin>> a;
q.push(a);
}
i64 ans = 0;
while(!q.empty())
{
int c = q.top();
q.pop();
if(q.empty())
{
std::cout<< ans << "\n";
}
else
{
int d = q.top();
q.pop();
ans += c + d;
q.push(d + c);
}
}
return 0;
}J题
题目要求:看前面能看到的牛牛的总和.
思路:从后向前看,并记录最高的牛牛,最高的牛牛后的不用管,直接退出数组,前的牛牛需记录.代码如下:
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin>> n;
std::vector<i64> a(n);
for(int i = 0;i <n;i++)
{
std::cin>> a[i];
}
i64 ans = 0;
std::vector<std::pair<int , int>> b;
std::vector<int> c(n);
for(int i = n - 1;i >= 0;i--)
{
while(!b.empty() && a[i] > b.back().first)
{
b.pop_back();
}
if(b.empty())
{
c[i] = n;
}
else
{
c[i] = b.back().second;
}
if(!b.empty() && a[i] == b.back().first)
{
b.pop_back();
}
b.emplace_back(a[i] , i);
}
for(int i = 0;i < n;i++)
ans+= c[i] - i - 1;
std::cout << ans << "\n";
return 0;
}K题
题目要求:给出若干个点,求最大互不平行线条数
思路:forfor循环加哈希表判断是否存在平行.代码如下:
#include<bits/stdc++.h>
using i64 = long long;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n;
std::cin>> n;
std::unordered_map<double , int> dg;
std::vector<std::pair<int , int>> ma(n + 1);
i64 ans = 0;
for(int i = 1;i <= n;i++)
{
std::cin>> ma[i].first >> ma[i].second;
}
for(int i = 1;i <= n;i++)
{
for(int j = i + 1;j <= n;j++)
{
double st = 0.0;
if(ma[i].second - ma[j].second != 0)
st = (double)(ma[i].first - ma[j].first) / (ma[i].second - ma[j].second);
else
st = 20000001.0;
if(dg.find(st) == dg.end())
{
ans++;
dg[st] = i * j + j;
}
else
{
continue;
}
}
}
std::cout<< ans <<"\n";
return 0;
}L题
题目要求:大富翁.
思路:跟着题目描述写,但需注意要在回合结束建筑给钱以及每次缴费和升级建筑都需判断是否为负,不然只能过60.代码如下:
#include<bits/stdc++.h>
using i64 = long long;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n , q , l;
i64 m;
std::cin >> n >> m >> q >> l;
std::vector<i64> nam(3 , m);
std::vector<std::pair<int , i64>> ma(n , {0 , 0}) , man(n , {0 , 0});
std::vector<i64> enhance((n + 1) * (l + 1));
for(int i = 0;i < n;i++)
{
for(int j = 0;j < l;j++)
{
std::cin>> enhance[i * l + j];
}
}
std::vector<i64> a(n);
for(int i = 0;i < n;i++)
{
std::cin>> a[i];
}
int x;
i64 y;
std::vector<std::pair<int , i64>> op(4 * q + 2, {0 , 0});
i64 k = 0;
while(std::cin>> x >> y && k <= 4 * q + 1)
{
op[k].first = x;
op[k].second = y;
k++;
}
int na = 0 , sum = 0;
std::vector<i64> w(3 , 0);
for(int i = 0;op[i].first;i++)
{
if(op[i].first == 1)
{
sum++;
if(na == 1)
na = 2;
else
na = 1;
int cn;
if(na == 1)
cn = 2;
else
cn = 1;
i64 bew = w[na];
w[na] += op[i].second;
w[na] %= n;
for(i64 j = bew + 1;j <= bew + op[i].second;j++)
{
int aw = j % n;
if(man[aw].first == na)
nam[na] += man[aw].second;
if(man[aw].first == cn)
{
nam[na] -= man[aw].second;
if(nam[na] < 0)
{
if(na == 1)
{
std::cout << "Renko" << "\n";
return 0;
}
else
{
std::cout<< "Merry" << "\n";
return 0;
}
}
nam[cn] += man[aw].second;
}
}
if(nam[na] < 0)
{
if(na == 1)
{
std::cout << "Renko" << "\n";
return 0;
}
else
{
std::cout<< "Merry" << "\n";
return 0;
}
}
if((i + 1 >= k || op[i + 1].first != 2) && sum == 2)
{
sum = 0;
for(int j = 0;j < n;j++)
{
if(ma[j].first == 1)
nam[1] += a[j];
if(ma[j].first == 2)
nam[2] += a[j];
}
if(nam[1] < 0)
{
std::cout<< "Renko" << "\n";
return 0;
}
if(nam[2] < 0)
{
std::cout<< "Merry" << "\n";
return 0;
}
}
}
else
{
int cn;
if(na == 1)
cn = 2;
else
cn = 1;
if(ma[w[na]].first == cn)
{
if(sum == 2)
{
sum = 0;
for(int j = 0;j < n;j++)
{
if(ma[j].first == 1)
nam[1] += a[j];
if(ma[j].first == 2)
nam[2] += a[j];
}
if(nam[na] < 0)
{
if(na == 1)
{
std::cout << "Renko" << "\n";
return 0;
}
else
{
std::cout<< "Merry" << "\n";
return 0;
}
}
}
continue;
}
if(ma[w[na]].first != cn)
{
int update = 0;
for(int j = ma[w[na]].second;update < op[i].second && j < l;j++)
{
if(nam[na] >= enhance[w[na] * l + j])
{
ma[w[na]].first = na;
ma[w[na]].second = j + 1;
man[w[na]].first = na;
man[w[na]].second += enhance[w[na] * l + j];
nam[na] -= enhance[w[na] * l + j];
update++;
if(nam[na] < 0)
{
if(na == 1)
{
std::cout << "Renko" << "\n";
return 0;
}
else
{
std::cout<< "Merry" << "\n";
return 0;
}
}
}
else
{
break;
}
}
}
if(sum == 2)
{
sum = 0;
for(int j = 0;j < n;j++)
{
if(ma[j].first == 1)
nam[1] += a[j];
if(ma[j].first == 2)
nam[2] += a[j];
}
if(nam[na] < 0)
{
if(na == 1)
{
std::cout << "Renko" << "\n";
return 0;
}
else
{
std::cout<< "Merry" << "\n";
return 0;
}
}
}
}
}
std::cout<< nam[1] << " " << nam[2] << "\n";
return 0;
}M题
题目要求:进库和出库,其进库时已有就直接输出一个,出库时没这个就输出最近的,存在两一样的就出最小的,库为空就输出empty.
思路:set建表,配合lower_bound即可,代码如下:
#include<bits/stdc++.h>
using i64 = long long;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int m;
std::cin>> m;
std::set<int> s;
while(m--)
{
int op , dg;
std::pair<std::set<int>::iterator , bool> pr;
std::cin>> op >> dg;
if(op == 1)
{
pr = s.insert(dg);
if(!pr.second)
std::cout<< "Already Exist" << "\n";
else
s.insert(dg);
}
else
{
if(s.empty())
{
std::cout<< "Empty" << "\n";
continue;
}
auto id = s.lower_bound(dg);
if(id == s.end())
{
id--;
std::cout<< *id << "\n";
s.erase(id);
continue;
}
else if(id == s.begin())
{
std::cout<< *id << "\n";
s.erase(id);
continue;
}
int r = *id;
id--;
int l = *id;
if(dg - l <= r - dg)
{
std::cout<< l << "\n";
s.erase(id);
}
else
{
std::cout<< r << "\n";
id++;
s.erase(id);
}
}
}
return 0;
}N题
题目要求:录入成绩,修改,删除和查询.
思路:建哈希表即可.代码如下:
#include<bits/stdc++.h>
using i64 = long long;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int m;
std::cin>> m;
std::unordered_map<std::string , i64> se;
while(m--)
{
int op;
std::cin>> op;
if(op == 1)
{
std::string nam;
i64 score;
std::cin>> nam >> score;
se[nam] = score;
std::cout<< "OK" << "\n";
}
else if(op == 2)
{
std::string nam;
std::cin>> nam;
if(se.find(nam) != se.end())
std::cout<< se[nam] << "\n";
else
std::cout<< "Not found" <<"\n";
}
else if(op == 3)
{
std::string nam;
std::cin>> nam;
if(se.find(nam) != se.end())
{
se.erase(nam);
std::cout<< "Deleted successfully" <<"\n";
}
else
{
std::cout<< "Not found" <<"\n";
}
}
else
{
std::cout<< se.size() << "\n";
}
}
return 0;
}
评论