NOIP2015普及组题目：
NOIP2018RP++ NOIP2016普及组题目 NOIP2018RP++T1 金币\((coin.cpp/c/pas)\)
题意
第一天，骑士收到一个金币，第二、三天，收到两个金币，第四、五、六天，收到三个金币......问\(k\)天，骑士一共收到几个金币？
数据范围
对于 100%的数据，\(1 ≤ K ≤ 10,000\)。
思路
这道题很水
看完数据范围，果断枚举啦。
废话不多说，我知道你们想看这个：（头文件就不传了，如果八道题都传的话，我的博客会变得很长。。。）
#define ll long longusing namespace std;inline ll read(){ char ch=getchar();ll res=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f;}inline void write(ll zx){ if(zx<0) zx=-zx,putchar('-'); if(zx<10) putchar(zx+'0'); else{ write(zx/10); putchar(zx%10+'0'); }}ll n,ans,k=0;int main(){ freopen("coin.in","r",stdin);freopen("coin.out","w",stdout); n=read(); //输入 for(ll i=1;k T2 扫雷游戏\((mine.cpp/c/pas)\)
题意
玩一下windows系统下的扫雷你就知道了。（手动滑稽）
每一个格子要不是雷，那就是数字。
雷：表示这个格子里有地雷。
数字：表示这个格子四周8个格子的雷的总数。
问：在某一个状态下，扫雷系统的状态。
数据范围
对于 100%的数据，\(1≤n≤100,1≤m≤100\)。
思路
这道题暴力就好了啊233333
这道题有两个思路：
1.枚举一下每一个格子，如果是数字，扫一遍其周围的格子，如果是雷，这个数字+1，如果是雷，那么就直接输出*。
2.枚举一下每一个格子，如果是雷，将四周的格子数字+1。最后输出的时候如果是雷，那么直接输出，否则输出之前累加的数字。
inline int read(){ char ch=getchar();int res=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f;}inline void write(int zx){ if(zx<0) zx=-zx,putchar('-'); if(zx<10) putchar(zx+'0'); else{ write(zx/10); putchar(zx%10+'0'); }}char a[110][110];int f[110][110];int n,m;void work(int x,int y){ f[x-1][y]++; f[x-1][y-1]++; f[x-1][y+1]++; f[x][y-1]++; f[x][y+1]++; f[x+1][y-1]++; f[x+1][y]++; f[x+1][y+1]++;}int main(){ freopen("mine.in","r",stdin);freopen("mine.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ char ch; cin>>ch; a[i][j]=ch; if(ch=='*') work(i,j); //采用方法2，如果是雷，拓展四周 } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='*') putchar('*'); //如果是雷 else write(f[i][j]); //如果是数字 } putchar('\n'); } return 0;} T3 求和 \((sum.cpp/c/pas)\)
题意
一条狭长的纸带被均匀划分出了\(n\)个格子，格子编号从\(1\)到\(n\)。每个格子上都染了一种颜色\(colori\)（用\([1,m]\)当中的一个整数表示），并且写了一个数字\(numberi\)。
定义一种特殊的三元组：\((x, y, z)\)，其中\(x,y,z\)都代表纸带上格子的编号
需要满足一下条件：
\(x,y,z\)都是整数,\(x<y<z\),\(y-x=z-y\)
\(colorx=colorz\)
问：所有满足以上条件的三元组的\((x + z) ∗ (??????? + ???????)\)之和为多少？
数据范围
对于第\(1\)组至第\(2\)组数据，\(1 ≤ n ≤ 100, 1 ≤ m ≤ 5\)；
对于第\(3\)组至第\(4\)组数据，\(1 ≤ n ≤ 3000, 1 ≤ m ≤ 100\)；
对于第\(5\)组至第\(6\)组数据，\(1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000\)，且不存在出现次数超过\(20\)的颜色；
对于全部\(10\)组数据，\(1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ colori ≤ m, 1 ≤ numberi ≤ 100000\)。
思路
对于20%的数据
直接枚举三元组(x、y、z)。
代码就不贴了。对于40%的数据
先将数组按顺序排序，枚举x、z判断一下y是否有解。
对于60%的数据
先将数组按顺序排序，将所有数字按颜色分组，再对于每个颜色进行暴力枚举，其他和40分方法一样。
对于100%的数据
这个时候就要使用到数学方法了。
先把数组中每个数字按照颜色分组。
根据\(y-x=z-y\)可以得出：\(2*y=z+x\)
那么等号的左边是一个偶数，等号右边也应该是一个偶数。
那么z、x应该同奇偶。那么一开始按颜色分组时，颜色相同，再按奇偶分组。
那么可以得出：
ans+=i*((num[a[i].color][i%2]-2)*a[i].number+sum[a[i].color][i%2])
其中num表示该颜色、奇偶所出现的次数，sum表示其数字之和。
#define MOD 10007 #define ll long longusing namespace std;inline ll read(){ char ch=getchar();ll res=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f;}inline void write(ll zx){ if(zx<0) zx=-zx,putchar('-'); if(zx<10) putchar(zx+'0'); else{ write(zx/10); putchar(zx%10+'0'); }}ll n,m,ans;struct node{ ll number,color;}a[100010];ll num[100010][5],sum[100010][5];int main(){ freopen("sum.in","r",stdin);freopen("sum.out","w",stdout); n=read();m=read(); for(ll i=1;i<=n;i++) a[i].number=read(); for(ll i=1;i<=n;i++) a[i].color=read(); for(ll i=1;i<=n;i++){ ++num[a[i].color][i%2]; sum[a[i].color][i%2]+=a[i].number; sum[a[i].color][i%2]%=MOD; } for(ll i=1;i<=n;i++){ ans+=i*((num[a[i].color][i%2]-2)*a[i].number+sum[a[i].color][i%2]); ans%=MOD; } write(ans);putchar('\n'); return 0;} T4 推销员\((salesman.cpp/c/pas)\)
题意
螺丝街一共有\(N\)家住户，第\(i\)家住户到入口的距离为\(Si\)米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的\(X\)家住户推销产品，然后再原路走出去。阿明每走\(1\)米就会积累\(1\)点疲劳值，向第\(i\)家住户推销产品会积累\(Ai\)点疲劳值。阿明是工作狂，他想知道，对于不同的\(X\)，在不走多余的路的前提下，他最多可以积累多少点疲劳值。
数据范围
对于 20%的数据，\(1≤N≤20\)；
对于 40%的数据，\(1≤N≤100\)；
对于 60%的数据，\(1≤N≤1000\)；
对于 100%的数据，\(1≤N≤100000\)。
思路
部分分
部分分其实就是枚举啦，可以用单调队列优化.....
100分做法
贪心其实就够了。
考虑我们如何将答案最大化：对于每个x，一定是选择(一个最大的s)+(x-1个最大的a)或者x个最大的a，可以使答案最优那么具体怎么实现呢
我们先把数组按照a排序 我们用sum[i]表示a数组的前i项的和，q[i]表示s数组的前i项的最大值，h[i]表示a[i]2+s[i]后i项的最大值，对于每个x，他的答案就是max(sum[x]+2q[x],sum[x-1]+h[x])
转自luogu的一位大佬。
#define ll long longusing namespace std;inline ll read(){ char ch=getchar();ll res=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f;}inline void write(ll zx){ if(zx<0) zx=-zx,putchar('-'); if(zx<10) putchar(zx+'0'); else{ write(zx/10); putchar(zx%10+'0'); }}ll n,h[100010],q1[100010],q2[100010];struct node{ ll s,v;}a[100010];bool cmp(node qx,node qy){return qx.v>qy.v;}int main(){ freopen("salesman.in","r",stdin);freopen("salesman.out","w",stdout); n=read(); for(ll i=1;i<=n;i++) a[i].s=read(); for(ll i=1;i<=n;i++) a[i].v=read(); sort(a+1,a+n+1,cmp); for(ll i=n;i>=1;i--) h[i]=max(h[i+1],2*a[i].s+a[i].v); for(ll i=1;i<=n;i++) q1[i]=max(q1[i-1],a[i].s); for(ll i=1;i<=n;i++) q2[i]=q2[i-1]+a[i].v; for(ll i=1;i<=n;i++) printf("%lld\n",max(q2[i-1]+h[i],q2[i]+2*q1[i])); return 0;} （占一个坑，以后再填NOIP2016）