洛谷3月月赛div2 题解（模拟+数学+贪心+数学）

由于本人太蒻了，div1的没有参加，胡乱写了写div2的代码就赶过来了。

T1 苏联人

题目背景

题目名称是吸引你点进来的。

这是一道正常的题，和苏联没有任何关系。

题目描述

你在打 EE Round 1，发现第一题非常无聊。于是你不打了，去下国际象棋了。

结果你发现，由于神秘力量的影响，你的棋子只剩下若干黑色的战车，若干黑色的主教和一只白色的国王了。

由于你很无聊，所以你把一些黑色棋子放在了 8×88\times 88×8 的棋盘上。

由于你很无聊，所以你想知道，国王放在哪些格子是安全的。换句话说，有哪些格子不会被战车和主教攻击到。当然，国王不能放在已经有棋子的地方。

为了防止你无聊透顶而不知道国际象棋的规则，这里给出以下提示（如果你知道规则那么可以跳过）：

国际象棋中，战车可以横向、竖向移动，且格数不受限制。但不能越过其他棋子。

如图，黄色的格子为战车能走到（攻击到）的格子。

国际象棋中，主教可以斜向移动，且格数不受限制。但不能越过其他棋子。

如图，黄色的格子为主教能走到（攻击到）的格子。

简单来说，如果当前位置到目标位置的直线上存在其他棋子，则可以称为“越过了其他棋子”。

如果目标位置是对方的棋子，那么移动到目标位置后，对方的棋子会被吃掉。

更进一步地，你要找的所有位置，必须满足没有黑色棋子能一步走到。

如果你还是没有读懂，可以结合样例进行理解。

输入格式

共 8 行，每行 8 个字符，表示棋盘的状态。

其中 . 表示空位，R 表示战车，B 表示主教。

————————————————————————————————————————————————-

根据题意模拟即可，数据比较水。

 #include<bits/stdc++.h>

 using namespace std;

 int a[][];

 int main()

 {

     for (int i=;i<=;i++)

         for (int j=;j<=;j++)

         {

             a[i][j]=;

             char ch;cin>>ch;

             if (ch=='B') a[i][j]=;

             else if (ch=='R') a[i][j]=;

         }

     for (int i=;i<=;i++)

         for (int j=;j<=;j++)

         {

             if (a[i][j]==||a[i][j]==) continue;

             if (a[i][j]==)

             {

                 for (int k=j-;k>=;k--)

                     if (a[i][k]==||a[i][k]==) break;

                     else a[i][k]=;

                 for (int k=j+;k<=;k++)

                     if (a[i][k]==||a[i][k]==) break;

                     else a[i][k]=;

                 for (int k=i-;k>=;k--)

                     if (a[k][j]==||a[k][j]==) break;

                     else a[k][j]=;

                 for (int k=i+;k<=;k++)

                     if (a[k][j]==||a[k][j]==) break;

                     else a[k][j]=;

             }

             if (a[i][j]==)

             {

                 for (int k=i-,l=j-;min(k,l)>=;k--,l--)

                     if (a[k][l]==||a[k][l]==) break;

                     else a[k][l]=;

                 for (int k=i+,l=j+;max(k,l)<=;k++,l++)

                     if (a[k][l]==||a[k][l]==) break;

                     else a[k][l]=;

                 for (int k=i+;i+j-k>=&&k<=;k++)

                     if (a[k][i+j-k]==||a[k][i+j-k]==) break;

                     else a[k][i+j-k]=;

                 for (int k=i-;k>=&&i+j-k<=;k--)

                     if (a[k][i+j-k]==||a[k][i+j-k]==) break;

                     else a[k][i+j-k]=;

             }

         }

     for (int i=;i<=;i++)

     {

         for (int j=;j<=;j++)

         if (a[i][j]==) cout<<;

         else cout<<;

         cout<<endl;

     }

     return ;

 }

T2 迫害

题目描述

有 kkk 个人，X 要对这 kkk 个人进行迫害。

这 kkk 个人，每一个人都拥有一个数字，分别从 111 至 kkk。

X 拥有 n+mn+mn+m 个数字，这些数字为 nnn 个 111 和 mmm 个大小可由 X 决定的数字（每个数字定好之后不能更换）。

X 能对这些人进行迫害，当且仅当他能用手中若干个数的加和等于被迫害人的数字，一次迫害就成功了（不会消耗数字）。

由于 X 的权利极大，又十分邪恶，他想要从第 111 个人开始一个一个进行迫害行动。

由于小 Z 也在这个被迫害的行列里，他十分的慌张，希望你来告诉他 X 能最多能从第一个人开始连续迫害多少个人。

由于被迫害的人太多了，所以请将答案对 100000000710000000071000000007 取模。

输入格式

第一行两个整数 n,mn,mn,m，表示 X 有 nnn 个 111，有 mmm 个大小可自定的数。

输出格式

请你告诉小 Z，X 能迫害多少个人。

--------------------------------------------------------------------------------------

可以发现这样的规律：

n=1

1 2 4 8 16……为最佳方案数

n=2

1 1 3 6 12 24……为最佳方案数

归纳得出方案总数为pow(2,m)*(n+1)-1，需要使用快速幂。

 #include<bits/stdc++.h>

 #define int unsigned long long

 using namespace std;

 int n,m;

 const int mod=;

 unsigned long long qcal(int a, int b) {

     int ans = , base = a;

     while (b != ) {

         if (b &  != )

 {

             ans *= base;

             ans%=mod;

 }

             base *= base;

             base%=mod;

             b >>= ;

             b%=mod;

     }

     return ans%mod;

 }

 signed main()

 {

     cin>>n>>m;

     unsigned long long ans=qcal(,m)*(n+);

     ans%=mod;

     printf("%lld",(ans-)%mod);

     return ;

  }

T3 代价

题目描述

给出一段序列，删数。代价为a[i-1]*a[i]*a[i+1]。求最小代价。

输入格式

第一行一个正整数 n。

第二行 n 个正整数，第 i个数表示 a[i+1]。

输出格式

一行一个正整数，表示最小的代价和。

-----------------------------------------------------------------------------

贪心比较显然，但关键是怎么贪？

以样例为例：

19 26 8 17

序列上实际是1 19 26 8 17 1

既然让代价最小，那我们可以让序列从一端出去，即ans+=a[i]*a[i+1]。因为不管怎样，相邻的两个数必有一乘，乘1能将代价最小化。

但实际上情况要复杂。序列中可能有无穷多个1。按照这种贪心策略，这时候的1是要分开处理的。所以我们不妨将两个1之间的序列单独处理。

具体可以看代码。

 #include<bits/stdc++.h>

 #define int long long

 using namespace std;

 int ans,a[],minn=0x3f3f3f3f,n,cnt;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if (ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 signed main()

 {

     n=read();

     a[]=a[n+]=;

     for (int i=;i<=n;i++){

         a[i]=read();

         minn=min(a[i],minn);

     }

     if (minn==)

     {

         minn=0x3f3f3f3f;

         for (int i=;i<=n+;i++)

         {

             if (a[i]==)

             {

                 ++cnt;

                 if (minn!=0x3f3f3f3f) ans+=minn,minn=0x3f3f3f3f;

                 continue;

             }

             minn=min(a[i],minn);

             if (a[i+]!=) ans+=1ll*a[i]*a[i+];

         }

         ans+=cnt-;

     }

     else{

         ans=minn;

         for (int i=;i<n;i++) ans+=1ll*a[i]*a[i+];

     }

     printf("%lld",ans);

     return ;

 }

T4 礼物

原题描述

-------------------------------------------------------------------------------------------------------

我事先并不知道正解是什么，如果洛谷出题解了，我会仔细看正解的，我的程序很慢很慢。

什么？证明？不存在的！我这种数学蒟蒻怎么会证明！

通过对n<=100的数据进行打表我们可以发现，ans=从1到num所有质数的乘积之和（除了被标记的质数）-1；

（其实是笔者手算了一大堆数据，现在感觉挺秃然的

所以我们现在可以愉快地写代码了。

你会惊奇地发现，全TLE了。

所以这就要考验各位OIer的人品和卡常技巧了。

1.八聚氧

#pragma GCC optimize(3)

#pragma GCC target("avx")

#pragma GCC optimize("Ofast")

#pragma GCC optimize("inline")

#pragma GCC optimize("-fgcse")

#pragma GCC optimize("-fgcse-lm")

#pragma GCC optimize("-fipa-sra")

#pragma GCC optimize("-ftree-pre")

#pragma GCC optimize("-ftree-vrp")

#pragma GCC optimize("-fpeephole2")

#pragma GCC optimize("-ffast-math")

#pragma GCC optimize("-fsched-spec")

#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("-falign-jumps")

#pragma GCC optimize("-falign-loops")

#pragma GCC optimize("-falign-labels")

#pragma GCC optimize("-fdevirtualize")

#pragma GCC optimize("-fcaller-saves")

#pragma GCC optimize("-fcrossjumping")

#pragma GCC optimize("-fthread-jumps")

#pragma GCC optimize("-funroll-loops")

#pragma GCC optimize("-fwhole-program")

#pragma GCC optimize("-freorder-blocks")

#pragma GCC optimize("-fschedule-insns")

#pragma GCC optimize("inline-functions")

#pragma GCC optimize("-ftree-tail-merge")

#pragma GCC optimize("-fschedule-insns2")

#pragma GCC optimize("-fstrict-aliasing")

#pragma GCC optimize("-fstrict-overflow")

#pragma GCC optimize("-falign-functions")

#pragma GCC optimize("-fcse-skip-blocks")

#pragma GCC optimize("-fcse-follow-jumps")

#pragma GCC optimize("-fsched-interblock")

#pragma GCC optimize("-fpartial-inlining")

#pragma GCC optimize("no-stack-protector")

#pragma GCC optimize("-freorder-functions")

#pragma GCC optimize("-findirect-inlining")

#pragma GCC optimize("-fhoist-adjacent-loads")

#pragma GCC optimize("-frerun-cse-after-loop")

#pragma GCC optimize("inline-small-functions")

#pragma GCC optimize("-finline-small-functions")

#pragma GCC optimize("-ftree-switch-conversion")

#pragma GCC optimize("-foptimize-sibling-calls")

#pragma GCC optimize("-fexpensive-optimizations")

#pragma GCC optimize("-funsafe-loop-optimizations")

#pragma GCC optimize("inline-functions-called-once")

#pragma GCC optimize("-fdelete-null-pointer-checks")

下面是代码

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<bitset>//压位用的，不然内存会爆炸，笔者用int时内存达到了1G

 using namespace std;

 int prime[],num;

 int n,m,c;

 int p[];

 bitset<>v;

 int main()

 {

     scanf("%d%d%d",&n,&m,&c);

     for (register int i=;i<=n;++i)//您需要灵活优化线性筛素数，才能防止被3e8的数据卡掉

     {

         if (!v[i]){

             prime[++num]=i;

         }

         if((!(i&))&&(i<<)<=n){

             v[i<<]=;

             continue;

         }

         for(register int j=;j<=num;j+=){

             if(i*prime[j]>n)break;

             v[i*prime[j]]=;

             if(!(i%prime[j]))break;

             if(j+>num)break;

             if(i*prime[j+]>n)break;

             v[i*prime[j+]]=;

             if(!(i%prime[j+]))break;

             if(j+>num)break;

             if(i*prime[j+]>n)break;

             v[i*prime[j+]]=;

             if(!(i%prime[j+]))break;

             if(j+>num)break;

             if(i*prime[j+]>n)break;

             v[i*prime[j+]]=;

             if(!(i%prime[j+]))break;

         }

     }

     for(register int i=;i<=m;i++){

         scanf("%d",&p[i]);

         if(p[i]==){//1肯定不行，因为上来就出错，a3=3

             printf("-1\n");

             return ;

         }

     }

     sort(p+,p+m+);//这里排序是为了更好地去重

     int now=;

     int ans=;

     for(register int i=;i<=num;++i){

         if(now<=m&&p[now]==i){

             while(now<=m&&p[now]==i)now++;

             continue;

         }

         ans=(1ll*ans*prime[i])%c;

     }

     printf("%d\n",(ans-+c)%c);

     return ;

 }

啊啊啊啊重复一遍我只是个蒟蒻，其实把这个代码发出来是为了给一点思路都没有的同学看的，咱别的不行，OI的基本操作咱还是要会的。

顺带一提，这道题我提交了43次才通过，名副其实的毒瘤题目。

巴特西

洛谷3月月赛div2 题解（模拟+数学+贪心+数学）

题目背景

题目描述

输入格式

题目描述

输入格式

输出格式

题目描述

输入格式

输出格式

最新文章

热门文章