题目大意：

你知道New Orange Industry Palatable公司吗？这是老板Smart为了与苹果公司竞争而新开的一家橘子公司，它的业务是栽培美味的橘子并售卖，公司简称为NOIP。 NOIP公司新推出N+1个橘子，每个橘子上都贴有一个标签，其中有N个普通的橘子上面印有一个”N”或”O”或”I”字母。还有一个独一无二的幸运橘子标签印有”P”字母。 NOIP公司搞了一个优惠活动，把N个普通橘子排成一排，从左到右依次编号为1～N。让顾客从左到右选三个橘子，如果依次排列组成了”NOI”，就可获得优惠券。Smart想把贴有标签P的幸运橘插入到排列中的（可以插入到队列的任意位置）。在换取优惠券时，P橘子可以作为N橘子或O橘子或I橘子使用。Smart想知道加入P橘子以后，第一个选购的顾客最多有多少种选法可以得到优惠券。



解题思路：

一系列骚操作。模拟+一系列优化、剪枝+骚操作



#include <cstdio>
#include <algorithm>
using namespace std;
char c[100005],l[3]={'N','O','I'};
int n,sI,sN,sO,ai,an,ao,a[100005],b[100005],ansum;
unsigned long long ans;
int main()
{
    //freopen("noip.in","r",stdin);
    //freopen("noip.out","w",stdout);
    scanf("%d\n",&n);gets(c);
    for(int i=0;i<n;i++)
     if(c[i]=='I') sI++;//先统计I的个数
    for(int i=0;i<n;i++)
     {
        if (c[i]=='N') sN++;a[i]=sN;//前面N的个数(包括本身)
        if (c[i]=='I') sI--;b[i]=sI;//后面I的个数(包括本身)
        if (c[i]=='O') ans+=a[i]*b[i],an+=sN,ai+=sI;//计算插入O会增加几个方案数~
     }
    for (int i=0;i<n;i++)ao=max(ao,a[i]*b[i]);//然后一系列比较(骚操作)
    ans+=max(ao,max(an,ai));//接着还是一系列比较(骚操作)
    printf("%llu",ans);//输出就OK了~
}

1008: Noip


Time Limit:1000MS    Memory Limit:32768KByte   64 IO Format:%I64d & %I64u

Description

一年一度的noip又开始，选手们比完赛后会在F盘下新建出很多的文件和文件夹。现在我们要根据要求收取其中的文件，请你写个程序帮我们计算一下收到了哪些文件。

Input


第一行一个整数T，表示有T组数据。

每组数据第一行两个整数N M，表示该组数据有N个文件，且收取了M次。

接着N行给出每个文件的绝对路径。

然后M行给出一条收取信息。

每条收取信息格式为

path S

表示收取path文件夹下扩展名为 S 的所有文件。 给出的path都是以\ 结束, S都是以.开头。



0 < T < 20, 0 < N <=100, 0 < M <= 100

所有的文件夹名，文件名，扩展名都由小写字母组成。


Output

对于每条收取信息，按文件输入的顺序输出满足条件的文件。

Sample Input

2
3 2
F:\exp.pas
F:\a\a.cpp
F:\a\a\a.c
F:\ .pas 
F:\a\ .c
3 2
F:\exp.pas
F:\a\a.cpp
F:\a\a\a.c
F:\ .c 
F:\a\ .pas



Sample Output

F:\exp.pas
F:\a\a\a.c
F:\a\a\a.c




[Submit]
 [Status]


#include<stdio.h>
#include<string.h>
struct node{
	char path[10000];
	int len;
}num[2000];
int main()
{
	int n, i, j, t, m;
	char name[10000], filetype[10000];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n, &m);
		for(i = 0; i < n; i++)
		{
			scanf("%s",num[i].path);
			num[i].len = strlen(num[i].path);
		}
		while(m--)
		{
			scanf("%s%s",name, filetype);
			for(i = 0; i < n; i++)
			{
				if(!(strstr(num[i].path, name) - num[i].path) && 
				num[i].len - (strstr(num[i].path, filetype) - num[i].path)== strlen(filetype))
					printf("%s\n",num[i].path);
			}
		}
	}
	return 0;
}

文章目录
分数
题目
T1: 【NOIP2020】water
代码
T2: 【NOIP2020】string
代码：
T3: 【NOIP2020】ball
T4: 【NOIP2020】walk
代码

分数
60（100）+32（32）+0（0）+25（30）=117（162）
题目

T1: 【NOIP2020】water
这是一个比较明显的拓扑，直接bfs或dfs模拟即可。

60是没打高精度，NOIP不给用__int128。

但我改题不想打就打了__int128.
代码
#include<cstdio>
#define Fu(i,a,b) for(register int i=(a);i<=(b);i++)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define LL __int128
LL z[100005],m[100005];
int n,s,d[100005][10],vis[100005];
bool bj=true;
LL gcd(LL a,LL b){
	LL r=a%b;
	while(r!=0) a=b,b=r,r=a%b;
	return b;
}
void add(LL &a,LL &b,LL a1,LL b1){
	LL r=gcd(b*b1,a*b1+a1*b);
	a=(a*b1+a1*b)/r,b=b*b1/r;
}
inline void print(LL x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
int main(){
//	fre(water);
	scanf("%d%d",&n,&s);
	Fu(i,1,n){
		scanf("%d",&d[i][0]);
		Fu(j,1,d[i][0]){
			scanf("%d",&d[i][j]);
			vis[d[i][j]]++;
		}
	}
	Fu(i,1,n){
		if(vis[i]==0) z[i]=1;
		m[i]=1;
	}
	while(bj){
		bj=false;
		Fu(i,1,n){
			if(d[i][0]!=0&&z[i]!=0){
				Fu(j,1,d[i][0]){
					add(z[d[i][j]],m[d[i][j]],z[i],m[i]*d[i][0]);
				}
				z[i]=0,m[i]=1;
			}
		}
		Fu(i,1,n)if(d[i][0]!=0&&z[i]!=0){
			bj=true;
			break;
		}
	}
	Fu(i,1,n) if(d[i][0]==0){
		print(z[i]);
		printf(" ");
		print(m[i]);
		printf("\n");
	}
	return 0;
}

T2: 【NOIP2020】string
不会正解，就打了一个暴力，结果…
代码：
#include<cstdio>
#include<cmath>
#define Fu(i,a,b) for(register int i=(a);i<=(b);i++)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int t,n,ans;
char a[1048580];
int find(int l,int r){
	int u[35],tot=0;
	Fu(i,1,30) u[i]=0;
	Fu(i,l,r) u[a[i]-'a'+1]++;
	Fu(i,1,30) if(u[i]%2==1) tot++;
	return tot;
}
int num(int i,int j){
	int tot=0;
	bool bj=true;
	Fu(l,1,j){
		Fu(k,1,i/j-1){
			if(a[(k-1)*j+l]!=a[k*j+l]){
				bj=false;
				break;
			}
		}
		if(!bj)break;
	}
	if(bj){
		Fu(k,1,j-1){
			if(find(1,k)<=find(i+1,n)){
				tot++;
			}
		}
	}
	return tot;
}
int main(){
//	fre(string);
	scanf("%d",&t);
	Fu(o,1,t){
		n=0,ans=0;
		a[++n]=getchar();
		while(a[n]<'a'||a[n]>'z')a[n]=getchar();
		while(a[n]>='a'&&a[n]<='z')a[++n]=getchar();n--;
		Fu(i,2,n-1){
			Fu(j,1,sqrt(i)){
				if(i%j==0){
					if(j!=i/j) ans+=num(i,j)+num(i,i/j);
					else ans+=num(i,j);
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

T3: 【NOIP2020】ball
无
T4: 【NOIP2020】walk
根据题意模拟就能30分，但我没有特判-1的情况，白掉5分。
代码
#include<cstdio>
#define Fu(i,a,b) for(register int i=(a);i<=(b);i++)
#define Fd(i,a,b) for(register int i=(a);i>=(b);i--)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
int n,k,a[15],w[15],b[15],tot;
int way[100005][2];
void dfs(int o){
	if(o>k){
		int c[15],ans=0;
		Fu(i,1,k)c[i]=b[i];
		bool bz=true;
		while(bz){
			Fu(i,1,n){
				c[way[i][0]]+=way[i][1];
				tot++;
				if(c[way[i][0]]>w[way[i][0]]||c[way[i][0]]<1){
					bz=false;
					break;
				}
			}
		}
		return ;
	}
	Fu(i,1,w[o]){
		b[o]=i;
		dfs(o+1);
	}
}
int main(){
//	fre(walk);
	scanf("%d%d",&n,&k);
	Fu(i,1,k) scanf("%d",&w[i]);
	Fu(i,1,n){
		scanf("%d%d",&way[i][0],&way[i][1]);
		a[way[i][0]]+=way[i][1];
	}
	int bj=0;
	Fu(i,1,k) if(a[i]!=0) bj=1;
	if(bj==0){
		printf("-1");
		return 0;
	}
	dfs(1);
	printf("%d",tot);
	return 0;
}

NOIP2018 提高
https://mp.weixin.qq.com/s/I8RggjLtxYfvYfzjycOFkA
NOIP2017 提高
https://mp.weixin.qq.com/s/LM8lW_UlbbeJ-ildCLOEtw
NOIP2016 提高
https://mp.weixin.qq.com/s/mn7Ks3LhRverZLfC9c23Fw
NOIP2015 提高
https://mp.weixin.qq.com/s/-lxY7bJhneDUCSqg6DIN8Q
NOIP2014 提高
https://mp.weixin.qq.com/s/YxozRDVILSsZXGdWMtAz6g
NOIP2013 提高
https://mp.weixin.qq.com/s/bdIt2EMmNCZxT5BVTeqe7g
NOIP2012 提高
https://mp.weixin.qq.com/s/SllBSQHinuC8DQ0C7liasA
NOIP2011 提高
https://mp.weixin.qq.com/s/ZQuBPwhfy52imRh7Q-CJ3w
NOIP2018 普及
https://mp.weixin.qq.com/s/6_DGjp0BTx2s7A_CXgJcCg
NOIP2017 普及
https://mp.weixin.qq.com/s/MOQq456HaeKjfZo8Fm6PIQ
NOIP2016 普及
https://mp.weixin.qq.com/s/8zkcLZhpigGA0Uzk9VQ5Ww
NOIP2015 普及
https://mp.weixin.qq.com/s/mDd3kwENhUTLfZkzT9SWZg
NOIP2014 普及
https://mp.weixin.qq.com/s/sSdsMOqT4ktb0Xo8RUa_9w
NOIP2013 普及
https://mp.weixin.qq.com/s/hCIQPieBbcL5L5F8zoJiVw