SDNU_ACM_ICPC_2021_Winter_Practice_7th [個人賽]
傳送門
L – 同餘方程
題意：
關於x的同餘方程ax三1（mod b）的最小正整數解。
思路：
板子題
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 500000 + 5
typedef long long ll ;
int x, y, a, b, k;
void exgcd(int a, int b)
{
if(!b)
{
x = 1;
y = 0;
return;
}
exgcd(b, a % b);
k = x;
x = y;
y = k - a / b * y;
return;
}
int main()
{
cin>>a>>b;
exgcd(a, b);
cout<<(x + b) % b<<endl;
return 0;
}
D – The Great Hero
題意：
英雄攻擊力為A，初始生命值為B，有n個怪物，對於每個怪物i，其攻擊力為ai，生命值為bi，如果英雄或怪物的生命值大於等於0，則說明其活著，否則死。問英雄能否在活著的情況下解決掉所有的怪物
思路1：
根據每個怪物的攻擊力進行升序排序，遍歷一遍，對最後一個怪物進行特判，看看能不能同歸於盡。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef long long ll ;
int t, A, B, n, q;
struct ran{
int a, b, wound;
}tr[MAX];//a代表攻擊力，b代表生命力
bool cmp(ran x, ran y){//攻擊力進行升序排序
if(x.a != x.b)
return x.a < y.a;
return x.b < y.b;//如果攻擊力相同就按生命力升序排序
}
inline int IntRead()//快讀
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-') w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
int main()
{
t = IntRead();
while (t--) {
q = 1;
A = IntRead();B = IntRead();n = IntRead();
for(int i = 1; i <= n; i++){
tr[i].a = IntRead();
}
for(int i = 1; i <= n; i++){
tr[i].b = IntRead();
}
sort(tr + 1, tr + 1 + n, cmp);//排序
for(int i = 1;i <= n; i++){
if(i == n){//特判
ll num1 = (B + tr[i].a - 1) / tr[i].a;//英雄能活幾次攻擊
ll num2 = (tr[i].b + A - 1) / A;//最後一個怪物能活幾次攻擊
if(num1 < num2)
q = 0;
break;
}
ll num = (tr[i].b + A - 1) / A;//怪物的攻擊次數
B -= num * tr[i].a;
if(B <= 0)
{
q = 0;
break;
}
}
if(q)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
思路2：
最後英雄的狀態有三種，一是生命力大於0，二是生命力小於0但同時怪物也死了，也就是同歸於盡，剩下的就是第三種情況，戰死且怪物沒死光。
對於第二種情況，英雄是挨了最後一下死掉，我們設英雄最後剩餘的生命力為x，那麼如果至少有一個怪物的攻擊力加上x大於0，就說明是贏了，這裡包括了兩種贏的情況。這個做法就是官方的方法，反正我沒想到 ，向大佬低頭 orz
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define MAX 100000 + 5
typedef long long ll ;
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-') w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0',
ch = getchar();
}
return s * w;
}
int ar[MAX], br[MAX];
int main()
{
ll t, a, b, n;
t = IntRead();
while (t--) {
int k = 0;
a = IntRead();
b= IntRead();
n = IntRead();
for(int i = 1; i <= n; i++)
{
ar[i] = IntRead();
}
for(int i = 1; i <= n; i++)
{
br[i] = IntRead();
}
ll sum = 0;
for(int i = 1; i <= n; i++)
{
sum += (br[i] + a - 1) / a * ar[i];//統計英雄得承受的所有傷害
}
for(int i = 1; i <= n; i++)
{
if(b - (sum - ar[i]) > 0)
{
k = 1;
}
}
if(k)
cout<<"YES\n";
else
cout<<"NO\n";
}
}
C – New Colony
題意：
巨石滾滾，k個巨石，滾在海拔不一的路上，如果tr[i]的海拔大於等於tr[i + 1]的海拔，則可以滾動，否則就停在i處給i處的海拔增1，問你底k個巨石會停在那個位置，如果滾出去了輸出-1
思路：
emmmm，一不小心被這個題卡的死死，瞄了一眼，以為複雜度太高，模擬會超時，就沒敢暴力寫，就死命找規律，說規律的吧也有，但是寫起來死麻煩，而且還得小型模擬一下，就放棄了，誰知道一看人家題解都是直接莽暴力，能過，而且時間還真他喵的短，給我整懵了orz
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef long long ll ;
int n, k, tr[105], p, q;
int main()
{
int t;
cin>>t;
while (t--) {
q = 1;
scanf("%d%d",&n, &k);
for(int i = 1; i <= n; ++i){
scanf("%d",&tr[i]);
}
for(int i = 1; i <= k && q; ++i){//循環k個石子
for(int j = 1; j <= n; j++){//找位置
if(j == n)//如果石子飛出去了，說明以後的石子都會飛出去，所以用q來調整一下循環和結果
{
q = 0;
break;
}
if(tr[j] < tr[j + 1]){
tr[j]++;//讓該處的海拔加1
p = j;//p來記錄此時的位置
break;
}
}
}
if(q)
cout<<p<<endl;
else
cout<<-1<<endl;
}
return 0;
}
I – Bad Hair Day
這個是我在過年前寫的單調棧的部落格上搞下來的，這裡就稍微偷點懶CV一下⁄(⁄ ⁄ ⁄ω⁄ ⁄ ⁄)⁄
題意：
就是數列tr，對每個數求其與大於大的第一個數之間的牛的個數，求總和
思路：
方向1:可以用單調棧對每個數tr[i]求得大於tr[i]的數的下標差減去1，然後求和。這種思路就和上面的模版差不多，兩種方法，一個順序一個逆序。
方向2:利用單調棧中剩餘元素的個數求和。舉個例子來講：12 10 9 11
開始時是12，然後10 小於12，可以入棧，在入棧之前，我們求一下棧內元素的數量，也就是1，將其加到sum里，現在棧變成了10 12，然後來個9，發現9小於10，可以入棧，入棧前我們再求一下棧內元素的數目，也就是2，加到sum里，再來個11，我們發現11大於9，也大於10，所以將9和10依次扔出去，再將11塞進去之前，再求一下棧的大小，加到sum裡面，最終得到sum的和為1 + 2 + 1.每次都要求棧大小的原因是，對於能塞進來的數，是小於棧內所有元素的，所以這棧內元素的每一個都多了一個小於他的數，最終加起來就可以得到答案
可能我講的亂七八糟的不太友好，但是理是這樣，想一會就明白了
方向1 — 順序：
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f//一個1e9多的數
#define MAX 3000000 + 5
typedef long long ll ;
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-') w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
int main()
{
ll n;
n = IntRead();
stack<ll>st;
for(int i = 0; i < n; i++)
tr[i] = IntRead();
tr[n] = inf;//這個題有些變化，如果一個數後面沒有比他大的數，那就不會算他後面的數，所以我們得讓棧內元素全扔出去，就在最後面加了一個最大值
ll sum = 0;
for(int i = 0; i <= n; i++)
{
while (!st.empty() && tr[i] >= tr[st.top()]) {//這個題和上面的題不太一樣，這個題如果被同等身高的人遮住了，就不能看見後面的，所以這裡是大於等於，遇到等於了就會停
sum += (i - st.top() - 1);
st.pop();
}
st.push(i);
}
cout<<sum<<endl;
return 0;
}
方向2:
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 3000000 + 5
typedef long long ll ;
inline int IntRead()
{
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-') w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
ll tr[MAX], k;
int main()
{
ll n, sum = 0;
n = IntRead();
stack<ll>st;
for(ll i = 1; i <= n; i++)
{
k = IntRead();
while (!st.empty() && k >= st.top()) {
st.pop();
}
sum += st.size();
st.push(k);
}
cout<<sum<<endl;
return 0;
}
H – How many
這個也是在年前什麼時候寫的，在寫的部落格裡面，這裡就CV一部分叭
題意：
給你一堆字元串，問你非同構字元串有幾個
思路：
對每個字元串都進行求最小表示法，將其塞到set中去重
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define MAX 100000 + 5
typedef long long ll;
map<string,int>mp;
set<string>se;
void getmin(string ss, ll m)
{
int i = 0, j = 1, k = 0, t;
while (i < m && j < m && k < m) {
t = ss[(i + k) % m] - ss[(j + k) % m];
if(t == 0)
k++;
else
{
if(t > 0) i += k + 1;
else j += k + 1;
if(i == j) j++;
k = 0;
}
}
int a = min(i, j);//取最小值
string sss = "";
for(int p = 0; p < m; p++)//字元串拼接，有個函數來著，但是我也不知道為什麼用不了
{
sss += ss[(p + a) % m];
}
se.insert(sss);
}
int main()
{
int n;
string s;
while (cin>>n) {
se.clear();//記得清0
for(int i = 1; i <= n; i++)
{
cin>>s;
ll m = s.size();
getmin(s, m);
}
cout<<se.size()<<endl;
}
}
還有兩個LCA的題，年前研究了半天也不是很懂，等以後再補叭
