传送门
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的题,年前研究了半天也不是很懂,等以后再补叭