2023年10月20日
Acwing3652 最大连续子序列
题目理解
代码实现
const int N = 1e5 + 10;
int w[N], f[N];
void solve()
{
int n;
while(cin >> n)
{
int g, t = 0, l = 0, r = 0;
memset(f, 0, sizeof f);
for(int i = 1; i <= n; i++)
cin >> w[i];
int res = -INF;
for(int i = 1; i <= n; i++)
{
f[i] = max(f[i - 1] + w[i], w[i]);
if(f[i - 1] < 0) t = i - 1;
if(f[i] > res) res = f[i], l = t, r = i - 1;
}
if(res < 0) cout << "0 0 0\n";
else cout << res << " " << l << " " << r << endl;
}
return;
}
第二种方法
const int N = 1e5 + 10;
int w[N], f[N];
void solve()
{
int n;
while(cin >> n)
{
int g, l, r;
memset(f, 0, sizeof f);
for(int i = 1; i <= n; i++)
cin >> w[i];
int res = -INF;
for(int i = n; i >= 1; i--)
{
if(w[i] >= f[i + 1] + w[i])
{
f[i] = w[i];
g = i;
}else
f[i] = f[i + 1] + w[i];
if(res <= f[i])
{
l = i;
res = f[i];
r = g;
}
}
if(res < 0) cout << "0 0 0\n";
else cout << res << " " << l - 1 << " " << r - 1 << endl;
}
return;
}
Acwing3715 交换次数
题目理解
可以在\(O(n^2)\)的时间解决，那么就直接冒泡来代表逆序对（这个题应该是顺序对）的数量
代码实现
const int N = 1010;
int a[N], cnt[N], b[N], res;
void solve()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i - 1; j++)
if(a[j] > a[i])
cnt[a[i]]++;
for(int i = 1; i <= n; i++) cout << cnt[i] << " ", res += cnt[i];
cout << endl << res;
return;
}
Acwing2074 倒计时
题目理解
用栈来存储即可。比较简单实现，也可以去直接写枚举。都是\(O(n)\)的复杂度
代码实现
const int INF = 0x3f3f3f3f;
int CNT = 1;
void clean(stack<int> &u)
{
while(!u.empty()) u.pop();
}
void solve()
{
int m, n;
cin >> m >> n;
stack<int> st;
int k, res = 0;
for(int i = 1; i <= m; i++)
{
cin >> k;
if(k == n && (int)st.size() == 0)
st.push(k);
else if(st.size() != 0 && k != st.top() - 1)
{
clean(st);
st.push(k);
}
else if(st.size() != 0 && k == st.top() - 1)
{
st.push(k);
if((int)st.size() == n)
{
res++;
clean(st);
}
}
}
cout << "Case #" << CNT << ": " << res << endl;
CNT++;
return;
}
Div.3 Round847 Polycarp and the Day of Pi
题目大意
问你给出的数字，有多少个数字是和\(Π\)相等的，最多不超30位。
题目理解
他已经给了你30位，直接复制做字符串匹配即可。
代码实现
string s = "314159265358979323846264338327";
void solve()
{
string n;
cin >> n;
int res = 0;
for(int i = 0, j = 0; i < n.size(); i++, j++)
if(n[i] == s[j])
res++;
else
break;
cout << res << endl;
return;
}
Div.3 Round847 B Taisia and Dice
题目大意
有\(n\)个骰子，然后会抛出，他们的和是\(S\)然后去掉一个最大值的骰子后，和是\(R\)，问骰子的原情况可能是什么？
题目理解
我们先用\(s - r\)计算出最大值的限制。然后再去贪心一下：
- 先全都变成最大的骰子
- 然后凑骰子的数量，用1来凑，骰子的数量。
- 就是加一减一，让总和不变，骰子多1，凑够\(n\)个骰子即可
代码实现
void solve()
{
int n, s, r;
cin >> n >> s >> r;
int m = s - r;
vector<int> res;
for(; s >= m; s -= m)
res.push_back(m);
if (s) res.push_back(s);
sort(res.begin(), res.end());
for(int i = 0; (int)res.size() < n;)
{
if (res[i] == 1) {
++i;
continue;
}
res[i]--;
res.push_back(1);
}
for(int i = 0; i < (int)res.size(); i++)
cout << res[i] << " ";
cout << endl;
return;
}