A-广告位招租中
考虑枚举每个gcd的值num。对于每个num，它的倍数经过gcd都可能成为它，于是我们统计每个num的倍数存在多少个（预处理后复杂度），然后从num=m开始遍历一遍找最大的k就可以了。这里有一个坑点：即使num的倍数有k个，也不一定能够得到gcd==num，比如2的倍数有4,4,8 然而gcd只能到达4.所以我们还需要用log的复杂度维护每个num的当前实际值。总复杂度为
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int cnt[N],num[N],a[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x]++;
}
for(int i=m;i<N;i++)
{
for(int j=i;j<N;j+=i)
{
cnt[i]+=a[j];
if(a[j]) num[i]=__gcd(num[i],j);
}
}
int maxx=0,ans=0;
for(int i=m;i<N;i++)
{
if(cnt[i]>maxx) maxx=cnt[i],ans=num[i];
else if(cnt[i]==maxx) ans=min(ans,num[i]);
}
cout<<maxx<<" "<<ans;
return 0;
}
B-MEX of MEXes
首先如果n=1，那么数组b为{2}，那么最后结果为1。
如果n>1，那么数组b一定包含1。很自然的，我们想数组b是否包含2，是否包含3，是否包含4......对于是否包含k来说，我们只需要找到数组a的一个非空连续子数组包含1到k-1且不包含k，就说明数组b包含k。那么我们找到包含1到k-1的长度最小的子数组，然后判断里面是否包含k即可。整个过程可以使用双指针实现，维护一个区间，区间初始左右端点为1的位置，再找到2的位置并更新区间左右端点，判断区间内是否包含3，再找3的位置......若此时考虑x的位置，那么区间更新后如果区间包含了x+1，那么就说明数组b中不可能存在x+1，最后答案即为x+1。特殊地，如果考虑了1到n都符合后，那么此时数组b为{1,2,3...n+1}，最后答案为n+2。
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
void solve(){
int n;
cin>>n;
vector<int> a(n);
vector<int> id(n+1);
for(int i=0;i<n;i++){
cin>>a[i];
id[a[i]]=i;
}
if(n==1){
cout<<1<<endl;
return;
}
int ans=1;
int l=n,r=-1;
while(ans<=n){
if(id[ans]>=l&&id[ans]<=r){
break;
}
l=min(l,id[ans]);
r=max(r,id[ans]);
ans++;
}
if(ans==n+1)
ans++;
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t=1;
while(t--){
solve();
}
}
C-战斗时回复
一个简单的极限问题，只需要考虑回复速度与伤害速度哪个大就可以了。要注意的是等号取不取得到的边界问题。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll T,H,t,n;
cin>>T>>H>>t>>n;
if(H*t<n*T) cout<<"hangeki";
else cout<<"kirito";
return 0;
}
D.小太阳的帕鲁世界Ⅰ
显而易见的是，有且只有一条可以到达 的路径，因此从
倒着走即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using i64 = long long;
const int inf = 1e9;
string s[2001];
int ans[2001][2001];
map<char, pair<int, int>> d;
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
ans[i][j] = inf;
for (int i = 0; i < n; i++)
cin >> s[i];
ans[n - 1][m - 1] = 0;
for (int x = n - 1, y = m - 1;;)
{
int xx = x + d[s[x][y]].first, yy = y + d[s[x][y]].second;
if (xx < 0 || xx >= n || yy < 0 || yy >= m)
break;
if (ans[xx][yy] <= ans[x][y] + 1)
break;
ans[xx][yy] = ans[x][y] + 1;
x = xx, y = yy;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cout << (ans[i][j] == inf ? -1 : ans[i][j]) << " \n"[j == m - 1];
cout << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
d['U'] = {1, 0};
d['D'] = {-1, 0};
d['L'] = {0, 1};
d['R'] = {0, -1};
int tc = 1;
// cin >> tc;
while (tc--)
solve();
return 0;
}
因为数据范围的原因，也可以直接搜索，可以通过本题。
E.小太阳的帕鲁世界Ⅱ
分析数据范围，不可能在每次询问中都 重新计算最小花费，因此考虑正方向和反方向的两次预处理，这样就能
进行查询了。
因为 的大小为
，即最大数据情况下要进行
次换行，使用
会导致一个较大的常数出现从而
，可以使用单调队列优化或者改用换行符来避免
，当然常数足够优秀的情况下使用优先队列以及
也不会导致
，如
所示。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve()
{
int n, k, q;
cin >> n >> k >> q;
vector<int> a(n, 1);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<i64> dp1(n), dp2(n);
auto work = [&](vector<i64> &dp)
{
priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<>> pq;
dp[0] = a[0];
pq.push({dp[0], 0});
for (int i = 1; i < n; i++)
{
while (pq.top().second + k < i)
pq.pop();
dp[i] = pq.top().first + a[i];
pq.push({dp[i], i});
}
};
work(dp1);
reverse(a.begin(), a.end());
work(dp2);
reverse(a.begin(), a.end());
reverse(dp2.begin(), dp2.end());
while (q--)
{
int x;
cin >> x;
x--;
cout << dp1[x] + dp2[x] - a[x] << endl;
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc--)
solve();
return 0;
}
F-又掉分了
贪心每次打表现分比当前分高的比赛即可。
因为可以看出，选择表现分比当前分低的比赛只会让当前分降低，只会让最后答案更劣。
具体地看，令a,b为两种情况的当前分，且a<b，令c为表现分。若c>b，那么a+<b+
，考虑取整，a+
<=b+
;若a<c<b，那么a会增加，但是不会等于或超过b。如此看来，当前分降低只会令答案更劣。
int类型自动向零取整。
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
void solve(){
int x,n;
cin>>x>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++){
if(a[i]>x){
x+=(a[i]-x)/2;
}
}
cout<<x<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t=1;
while(t--){
solve();
}
}
G. Birusu的公园
单调队列
将数组复制一倍
维护距离当前节点小于n的单调队列，每次检查队列末尾的 +
是否不大于
，不大于则取出(每次向后拓展时，队列中的值都会
,保证队列单调性 )。
用队头更新答案。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define rept(i, a, ne) for(int i = (a); i !=-1; i=ne[i])
#define debug(x) cout<<#x<<": "<<x<<endl
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int>PII;
const int N=2e5+10;
int a[N];
void slove()
{
deque<int>qu;
int n;
cin>>n;
rep(i,1,n)
{
cin>>a[i];
a[i+n]=a[i];
}
int ma=0;
rep(i,1,2*n)
{
while(qu.size()&&i-qu.front()>=n)
qu.pop_front();
if(qu.size())
ma=max(ma,a[i]+a[qu.front()]+i-qu.front()-1);
while(qu.size()&&a[i]>=a[qu.back()]+i-qu.back())
qu.pop_back();
qu.push_back(i);
}
cout<<ma;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
// cin>>t;
while(t--)
{
slove();
}
return 0;
}
H. 被诅咒的宝藏
根据题意我们易知如果可以拿走 个宝藏，那么肯定可以拿走
个宝藏，故我们直接二分答案，根据题意增加重量后排序，再暴力拿取宝藏，判断总克数是否超过了
，找出最大可拿宝藏数即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long a[N], s, b[N], sum;
int main() {
long long n;
cin >> n >> s;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
long long l = 0, r = n;
while(l < r) {
long long mid = (l + r + 1) >> 1;
for(int i = 1; i <= n; i++) {
b[i] = a[i] + mid * i;
}
sort(b + 1, b + n + 1);
sum = 0;
for(int i = 1; i <= mid; i++) {
sum += b[i];
if(sum > s)
break;
}
if(sum > s)
r = mid - 1;
else
l = mid;
}
for(int i = 1; i <= n; i++) {
b[i] = a[i] + l * i;
}
sort(b + 1, b + n + 1);
sum = 0;
for(int i = 1; i <= l; i++) {
sum += b[i];
}
cout << l << ' ' << sum;
return 0;
}
I. 决定命运的博弈
当 和
互质时，
也与
互质。考虑到题目保证
，因此
必胜。 （题目本质来源于zhihu.com）
#include<bits/stdc++.h>
using namespace std;
int main() {
cout << "Tpdjbmjtn";
}
小彩蛋：大家可以把两个高手的名字中的字母都替换成单词表中的前一个单词（本题图片为黄新波大师的《全世界无产者联合起来》）。
52Hz的minmax区间（easy）
很明显最大值和最小值的价值可以分开计算，当一个数为最大值时，左右两边不能有比他大的数，依次从大往小加入，同时找出左右存在的最近的元素计算价值即可，最小值同理
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=500010;
const ll mod=998244353;
//const ll mod=1e9+7;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define vi vector <int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long
#define i128 __int128
#define pb emplace_back
#define pii pair<int,int>
#define debug(x) std::cout<<x<<endl
#define endl '\n'
#define mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
template<typename type>
inline void read(type &x)
{
x=0;bool flag(0);char ch=getchar();
while(!isdigit(ch)) flag=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
flag?x=-x:0;
}
template<typename type>
inline void write(type x,bool mode=1)//0为空格，1为换行
{
x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
do Stack[++top]=x%10,x/=10; while(x);
while(top) putchar(Stack[top--]|48);
mode?putchar('\n'):putchar(' ');
}
//head~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//begin~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//end~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int n,pos[N];
ll ans=0;
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
pos[x]=i;
}
set<int> sq;
sq.insert(0);
sq.insert(n+1);
for(int i=n;i>=1;i--){
int w=pos[i];
auto x=sq.lower_bound(w);
ll r=*x;
x--;
ll l=*(x);
ans+=(r-w)*(w-l)*w;
sq.insert(pos[i]);
ans%=mod;
}
sq.clear();
sq.insert(0);
sq.insert(n+1);
for(int i=1;i<=n;i++){
int w=pos[i];
auto x=sq.lower_bound(w);
ll r=*x;
x--;
ll l=*(x);
ans-=(r-w)*(w-l)*w;
sq.insert(pos[i]);
ans%=mod;
}
cout<<(ans%mod+mod)%mod;
}
int main()
{
int _=1;
while(_--){
solve();
}
return 0;
}
52Hz的minmax区间（hard）
和区间1最大不一样在于，最大最小值不能分开计算
考虑计算最大值小于最小值位置或者大于最小值位置的情况
当我们从大向小加入数时，选择左右两端中长度较小的一段，并且二分另一边所能到达的最远距离，计算这样的区间个数，那么剩下的区间则都是和当前情况相反的距离
并且选择左右两端中长度较小的一段，整体所需要扫的最多次数是nlogn的级别，再扫另一个所能到达最远距离用二分进行优化，最后的时间复杂度为nlognlogn
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=200010;
const ll mod=998244353;
//const ll mod=1e9+7;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define vi vector <int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long
#define i128 __int128
#define pb emplace_back
#define pii pair<int,int>
#define debug(x) std::cout<<x<<endl
#define endl '\n'
#define mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
template<typename type>
inline void read(type &x)
{
x=0;bool flag(0);char ch=getchar();
while(!isdigit(ch)) flag=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
flag?x=-x:0;
}
template<typename type>
inline void write(type x,bool mode=1)//0为空格，1为换行
{
x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
do Stack[++top]=x%10,x/=10; while(x);
while(top) putchar(Stack[top--]|48);
mode?putchar('\n'):putchar(' ');
}
//head~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//begin~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//end~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ll pos[N],n,st[22][1000010],lg[1000010],a[N];
ll ans;
set<int> sq;
ll query(ll l,ll r){
if(l>r){
swap(l,r);
}
ll len=lg[r-l+1];
return min(st[len][l],st[len][r-(1<<len)+1]);
}
ll query_max(ll l,ll r){
if(l>r){
swap(l,r);
}
ll len=lg[r-l+1];
return max(st[len][l],st[len][r-(1<<len)+1]);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
pos[a[i]]=i;
st[0][i]=a[i];
}
for(int j=1;j<=20;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[j][i]=min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
}
for(int i=2;i<1000010;i++){
lg[i]=lg[i/2]+1;
}
sq.insert(0);
sq.insert(n+1);
for(int i=n;i>=1;i--){
int w=pos[i];
auto x=sq.lower_bound(w);
ll r=*x;
x--;
ll l=*x;
ll sum=0;
ll minn=1e18;
if(w-l<r-w){
for(int j=w;j>l;j--){
minn=min(minn,a[j]);
if(minn<query(w,r-1)){
sum+=r-w;
continue;
}
ll l1=w,r1=r-1;
while(l1<r1){
int mid=(l1+r1)>>1;
if(query(w,mid)<minn){
r1=mid;
}else{
l1=mid+1;
}
}
if(l1>=r){
l1--;
}
if(query(w,l1+1)>minn&&l1+1<r){
l1++;
}
if(query(l1,w)<minn){
l1--;
}
sum+=l1-w+1;
}
sum--;
ans+=sum*w-((r-w)*(w-l)-1-sum)*w;
ans%=mod;
}else{
for(int j=w;j<r;j++){
minn=min(minn,a[j]);
if(minn<query(l+1,w)){
sum+=w-l;
continue;
}
ll l1=l+1,r1=w;
while(l1<r1){
int mid=(l1+r1)>>1;
if(query(mid,w)<minn){
l1=mid+1;
}else{
r1=mid;
}
}
if(l1<=l){
l1++;
}
if(query(l1-1,w)>minn&&l1>l+1){
l1--;
}
if(query(l1,w)<minn){
l1++;
}
sum+=(w-l1+1);
}
sum--;
ans+=((r-w)*(w-l)-1-sum)*w-sum*w;
ans%=mod;
}
sq.insert(pos[i]);
}
for(int i=1;i<=n;i++){
pos[a[i]]=i;
st[0][i]=a[i];
}
for(int j=1;j<=20;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[j][i]=max(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
}
sq.clear();
sq.insert(0);
sq.insert(n+1);
for(int i=1;i<=n;i++){
int w=pos[i];
auto x=sq.lower_bound(w);
ll r=*x;
x--;
ll l=*x;
ll sum=0;
ll maxn=0;
if(w-l<r-w){
for(int j=w;j>l;j--){
maxn=max(maxn,a[j]);
if(maxn>query_max(w,r-1)){
sum+=r-w;
continue;
}
ll l1=w,r1=r-1;
while(l1<r1){
int mid=(l1+r1)>>1;
if(query_max(w,mid)>maxn){
r1=mid;
}else{
l1=mid+1;
}
}
if(l1>=r){
l1--;
}
if(query_max(w,l1+1)<maxn&&l1+1<r){
l1+=1;
}
if(query_max(l1,w)>maxn){
l1--;
}
sum+=l1-w+1;
}
sum--;
ans+=sum*w-((r-w)*(w-l)-1-sum)*w;
ans%=mod;
}else{
for(int j=w;j<r;j++){
maxn=max(maxn,a[j]);
if(maxn>query_max(l+1,w)){
sum+=w-l;
continue;
}
ll l1=l+1,r1=w;
while(l1<r1){
int mid=(l1+r1)>>1;
if(query_max(mid,w)>maxn){
l1=mid+1;
}else{
r1=mid;
}
}
if(l1<=l){
l1++;
}
if(query_max(l1-1,w)<maxn&&l1-1>l){
l1--;
}
if(query_max(l1,w)>maxn){
l1++;
}
sum+=w-l1+1;
}
sum--;
ans+=((r-w)*(w-l)-1-sum)*w-sum*w;
ans%=mod;
}
sq.insert(pos[i]);
}
ans+=mod;
cout<<ans%mod<<endl;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _=1;
while(_--){
solve();
}
return 0;
}
L. Kaiou的笑话
贪心
对于每一个 贪心的找到前一个
(对于
最近)的前一个
(对于
最近)的位置 或者 前一个
(对于
最近) 的前一个
(对于
最近) 的位置。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define rept(i, a, ne) for(int i = (a); i !=-1; i=ne[i])
#define debug(x) cout<<#x<<": "<<x<<endl
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int>PII;
void slove()
{
int n;
string s;
cin>>n>>s;
s='0'+s;
int lh=0,lt=0,le=0,la=0,se=0,sa=0;
int mi=INT_MAX;
rep(i,1,n)
{
if(s[i]=='t')
lt=i;
if(s[i]=='h')
lh=i;
if(s[i]=='a'&&lh)
la=i,sa=i-lh-1;
if(s[i]=='e'&<)
le=i,se=i-lt-1;
if(s[i]=='n')
{
if(la)
mi=min(mi,i-la-1+sa);
if(le)
mi=min(mi,i-le-1+se);
}
}
if(mi==INT_MAX)
cout<<-1;
else
cout<<mi;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
// cin>>t;
while(t--)
{
slove();
}
return 0;
}
M-大生
输出任意非空字符串即可。
“所谓大生，就是不搞学习的大学生。” 这句话出自本校一位可敬的概率论老师。
本想收集大家的校训，但是大家似乎都答了"我不知道"？
本校还有一位选手在比赛接近尾声的时候回来交了一发"原神启动"
下面是收集到的一些校训（可能有看漏的）
崇真尚美
知行统一，博厚悠远
勤奋严谨，求实创新
自立立人，兴安安国
笃信好学，自然宽和
海纳百川，取则行远
崇德尚善，精工铸新
厚德尚能，博学笃行
求学问是，敢为人先
有为有守，不忮不求
自然宽和，笃信好学
求学问是，敢为人先
求实求真，大气大为
尚德，尚学，尚行；爱国，爱校，爱人
献身、求实、团结、奋进
明德仁爱，博学至善
忠信笃敬
广学坚守，勤思敏行
立德 尚能 善学 笃行
品质至上
下面是本场比赛的一些有趣的回答
ÎÒ²»ÖªµÀ
大学大学，大不了自学
Hello, World!
鸡你太美
i am iron man
红烧鸡翅我最爱吃
原神启动
我是神里绫华的狗
加训加训
我知道但是我测一下是不是输出什么都可以通过
京公网安备 11010502036488号