给一个string,和一些query, 求每个query中, string展开后的长度.
这题就是pre sum. 秒了
#include "bits/stdc++.h"
using namespace std;
int main() {
int N,Q;
cin >> N >> Q;
string s;
cin >> s;
int dp[N + 1];
for(int i = 1; i <= N; i++)
{
dp[i] = dp[i - 1] + (int)(s[i - 1] - 'a') + 1;
}
while (Q--)
{
int l,r;
cin >> l >> r;
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}设计一个比赛, 一共n个人, 每个人是固定时间间隔后开始比赛, 然后比赛的总长度是k, 求每个人的比赛的时候, 有多少人还没有完成比赛.
这题画画图就明白了, 但是要注意几个corner cases. 比如间隔给的长度小于比赛的长度等.
#include "bits/stdc++.h"
using namespace std;
int main() {
int K;
cin >> K;
while (K--)
{
int64_t N,X,T;
cin >> N >> X >> T;
int64_t B = min(N, T/X);
if (X <= T)
{
if (N < T/X)
{
cout << N*(N - 1) / 2 << endl;
}
else
{
int64_t p1 =(N - T/X - 1) * (T/X);
int64_t p2 = (T/X) * (T/X + 1) / int64_t(2.0);
cout << p1 + p2 << endl;
}
}
else
{
cout << 0 << endl;
}
}
return 0;
}给一个2d矩阵, 一个人的位置, 求矩阵上的两个点, 让这个人走的最远.
这题啥了, 最远的两个点, 当然是对角线. 哎….贴个比赛的code吧.
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <deque>
using namespace std;
int main() {
int T;
cin >> T;
while (T --)
{
int N,M,I,J;
cin >> N >> M >> I >> J;
auto dis = [&] (int x1, int y1, int x2, int y2) -> int64_t {
if(x1 == x2 && y1 == y2){
return -1;
}
return abs(x2 - x1) + abs(y2 - y1);
};
vector<pair<int64_t, pair<int, int>>> v;
int64_t a1 = dis(1, 1, I, J);
int64_t a2 = dis(N, M, I, J);
int64_t a3 = dis(1, M, I, J);
int64_t a4 = dis(N, 1, I, J);
v.push_back(make_pair(a1, make_pair(1, 1)));
v.push_back(make_pair(a2, make_pair(N, M)));
v.push_back(make_pair(a3, make_pair(1, M)));
v.push_back(make_pair(a4, make_pair(N, 1)));
sort(v.begin(), v.end());
cout << to_string(v[3].second.first) + " " + to_string(v[3].second.second);
int64_t b1 = dis(1, 1, v[3].second.first, v[3].second.second);
int64_t b2 = dis(N, M, v[3].second.first, v[3].second.second);
int64_t b3 = dis(1, M, v[3].second.first, v[3].second.second);
int64_t b4 = dis(N, 1, v[3].second.first, v[3].second.second);
vector<pair<int64_t, pair<int, int>>> vv;
vv.push_back(make_pair(b1, make_pair(1, 1)));
vv.push_back(make_pair(b2, make_pair(N, M)));
vv.push_back(make_pair(b3, make_pair(1, M)));
vv.push_back(make_pair(b4, make_pair(N, 1)));
sort(vv.begin(), vv.end());
cout << " "+ to_string(vv[3].second.first) + " " + to_string(vv[3].second.second) << endl;
}
return 0;
}给一个数组, 可以加n个非负数数字, 让他的算术平均数等于项数. 问n是几?
这题题中给了已知永远有答案, 所以想了想就知道, 是比较sum和项数. 因为我们加的是非负数,所以可以加0来在不增加算术平均数的情况下, 增加项数.
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <deque>
using namespace std;
int main() {
int T;
cin >> T;
while (T --)
{
int N;
cin >> N;
int A[N];
for(int i = 0; i < N; i++)
cin >> A[i];
int64_t sum = 0;
for(int i = 0; i < N; i++){
sum += A[i];
}
if (sum == N)
{
cout << "0" << endl;
}
else if (sum > N) {
cout << sum - N << endl;
}
else{
cout << "1" << endl;
}
}
return 0;
}#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
const int N = 5010;
pii v[N];
int A[N];
int dp[N];
int main() {
int n;
int res = 0;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> A[i];
}
for(int i = 1; i <= n; i++) {
dp[i] = A[i];
for(int j = 1; j < i; j++) {
if (A[j] < A[i])
{
dp[i] = max(dp[i], dp[j] + A[i]);
}
}
res = max(res, dp[i]);
}
cout << res << endl;
return 0;
}#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
const int N = 5010;
pii v[N];
int A[N];
int dp[N];
int main() {
int n;
int res = 0;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> v[i].first >> v[i].second;
}
sort(v+1, v + n + 1);
for(int i = 1; i<= n; i++) {
dp[i] = 1;
for(int j = 1; j < i; j++){
if (v[j].second < v[i].second)
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
cout << res << endl;
return 0;
}最长上升子序列(LIS) + 最长下降子序列(LDS) 模板题.
dp[i] 定义的是以A[i]为最后一个元素的最长上升(下降)子序列.
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 120;
int A[N];
int dp[N];
int main() {
int T;
cin >> T;
while (T --)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> A[i];
}
int res = 0;
for(int i = 1; i <= n; i++) {
dp[i] = 1;
for(int j = 1; j < i; j++) {
if (A[j] < A[i])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
for(int i = n; i > 0; i --) {
dp[i] = 1;
for(int j = n; j > i; j--) {
if (A[i] > A[j])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
cout << res << endl;
}
return 0;
}这题和方格取数一样, 都是2d的dp问题.
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
#define fio ios::sync_with_stdio(0);cin.tie(0)
#define nfio cin.tie(0)
int m[101][101];
int dp[101][101];
int main() {
fio;
nfio;
int N;
cin >> N;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
int t;
cin >> t;
m[i][j] = t;
}
}
auto dfs =[&](auto dfs, int i, int j) -> int {
if (dp[i][j] > 0)
{
return dp[i][j];
}
if (i == 0 || j == 0)
{
return INT_MAX / 2;
}
if (i == 1 && j == 1)
{
return m[i][j];
}
int res = INT_MAX;
res = min(res, dfs(dfs, i - 1, j) + m[i][j]);
res = min(res, dfs(dfs, i, j - 1) + m[i][j]);
dp[i][j] = res;
return res;
};
cout << dfs(dfs, N, N) << endl;
return 0;
}A
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int main() {
const double m = 100.0;
int A,B;
cin >> A >> B;
double b = B / m;
cout << A * b << endl;
return 0;
}B
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <unordered_set>
using namespace std;
int main() {
int N;
cin >> N;
unordered_set<int> set;
for (int i = 0; i < N; i++)
{
int t;
cin >> t;
set.emplace(t);
}
bool miss = false;
for(int i = 1; i <= N; i++) {
if (set.find(i) == set.end())
{
miss = true;
break;
}
}
if (miss)
{
cout << "No" << endl;
}
else {
cout << "Yes" << endl;
}
return 0;
}C
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <unordered_set>
using namespace std;
int main() {
int64_t A,B,C;
cin >> A >> B >> C;
if (!(C & 1)) // if C is even
{
if (abs(A) < abs(B))
{
cout << "<" << endl;
}
else if (abs(A) > abs(B))
{
cout << ">" << endl;
}
else
{
cout << "=" << endl;
}
}
else // if C is odd
{
if (A < B)
{
cout << "<" << endl;
}
else if (A > B)
{
cout << ">" << endl;
}
else
{
cout << "=" << endl;
}
}
return 0;
}D
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, Q;
cin >> N >> Q;
vector<int64_t> v;
for(int i = 0; i < N; i++) {
int64_t t;
cin >> t;
v.push_back(t);
}
// count how many available number from [1,+] without in v and before v[i];
//
vector<int64_t> vv;
for(int i = 1; i<= N; i++) {
vv.push_back(v[i - 1] - i);
}
while (Q --)
{
int64_t q;
cin >> q;
int j = lower_bound(vv.begin(), vv.end(), q) - vv.begin();
if (j == N) // if q is outside of vv
{
cout << v[N - 1] + q - vv[N - 1] << endl;
}
else
{
cout << v[j] - vv[j] + q - 1 << endl;
}
}
return 0;
}给两个数字l和r, 求从l加到r中间digit的变化个数是多少.
这题用的方法和D一样,就是先求R的答案, 然后减去L的答案, 具体的求法是通过观察: 比如21这个数, 从1->9 是9个1位改变, 9->10是1个2位, 10->19是9个1位改变, 19->20是2个1位改变. 20->21 是1个1位改变, 所以加起来就是21+2, 有次可推,数字123是123+12+1.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while (t --)
{
int l,r;
cin >> l >> r;
auto count = [&](int n) -> int64_t {
int base = 10;
int digit = 1;
int64_t res = 0;
while (n)
{
res += n;
n /= base;
}
return res;
};
cout << count(r) - count(l) << endl;
}
return 0;
}