1890：【15NOIP提高组】跳石头
时间限制: 1000 ms 内存限制: 131072 KB
提交数: 1037 通过数: 561
【题目描述】
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳 跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M块岩石(不能 移走起点和终点的岩石)。
【输入】
一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终 点之间的岩石数,以及组委会至多移走的岩石数。
接下来N行,每行一个整数,第i行的整数 Di(0 < Di < L)表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
【输出】
只包含一个整数,即最短跳跃距离的最大值。
【输入样例】
25 5 2
2
11
14
17
21
【输出样例】
4
【提示】
输入输出样例1说明：将与起点距离为2和14的两个岩石移走后,最短的跳跃距离为4(从与起点距离17的岩石跳到距离21的岩石,或者从距离21的岩石跳到终点)。
其它输入输出样例下载
数据范围：
对于20%的数据,0 ≤ M ≤ N ≤ 10。
对于50%的数据,0 ≤ M ≤ N ≤ 100。
对于100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。
#include<iostream>
#include<cstdio>
using namespace std;
int leng,n,m,a[50002];
bool check(int x){
int last=0;
int sum=0;
for(int i=1;i<=n;i++){
if(a[i]-last>=x){
last=a[i];
}else{
sum++;
}
}
if(leng-last<x){
sum++;
}
return sum<=m;
}
int main(){
cin>>leng>>n>>m;
int l=1,r=leng;
for(int i=1;i<=n;i++){
cin>>a[i];
}
while(r>l){
int mid=(l+r+1)>>1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
cout<<l;
return 0;
}
1891：【15NOIP提高组】子串
时间限制: 1000 ms 内存限制: 131072 KB
提交数: 244 通过数: 136
【题目描述】
有两个仅包含小写英文字母的字符串AA和BB。现在要从字符串AA中取出kk个互不重叠的非空子串,然后把这kk个子串按照其在字符串AA中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串BB相等?注意:子串取出的位置不同也认为是不同的方案。
【输入】
第一行是三个正整数 n,m,kn,m,k,分别表示字符串AA的长度,字符串BB的长度,以及问题描述中所提到的kk,每两个整数之间用一个空格隔开。 第二行包含一个长度为nn的字符串,表示字符串 AA。第三行包含一个长度为mm的字符串,表示字符串BB。
【输出】
输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求输出答案对 1,000,000,0071,000,000,007 取模的结果。
【输入样例】
6 3 1
aabaab
aab
【输出样例】
2
【提示】
样例2：
输入：
6 3 2
aabaab
aab
输出：
7
样例3：
输入：
6 3 3
aabaab
aab
输出：
7
输入输出样例说明：
所有合法方案如下：（加下划线的部分表示取出的子串）
其它输入输出样例下载
数据规模与约定：
对于第1组数据:1≤n≤500,1≤m≤50,k=11≤n≤500,1≤m≤50,k=1;
对于第2组至第3组数据:1≤n≤500,1≤m≤50,k=21≤n≤500,1≤m≤50,k=2;
对于第4组至第5组数据:1≤n≤500,1≤m≤50,k=m1≤n≤500,1≤m≤50,k=m;
对于第1组至第7组数据:1≤n≤500,1≤m≤50,1≤k≤m1≤n≤500,1≤m≤50,1≤k≤m;
对于第1组至第9组数据:1≤n≤1000,1≤m≤100,1≤k≤m1≤n≤1000,1≤m≤100,1≤k≤m;
对于所有10组数据:1≤n≤1000,1≤m≤200,1≤k≤m1≤n≤1000,1≤m≤200,1≤k≤m。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define P 1000000007
using namespace std;
int n,m,K,t=1;
int f[2][205][205][2];
char A[1005],B[205];
int add(int x,int y) {return x+y>=P?x+y-P:x+y;}
int dec(int x,int y) {return x-y< 0?x-y+P:x-y;}
int mul(int x,int y) {return 1ll*x*y%P;}
int main(){
scanf("%d%d%d",&n,&m,&K);
scanf("%s%s",A+1,B+1);
f[0][0][0][0]=1;
for(int i=1;i<=n;++i){
f[t][0][0][0]=1;
for(int j=1;j<=m;++j){
for(int k=1;k<=m;++k){
f[t][j][k][0]=add(f[t^1][j][k][0],f[t^1][j][k][1]);
f[t][j][k][1]=(A[i]==B[j])?add(add(f[t^1][j-1][k][1],f[t^1][j-1][k-1][1]),f[t^1][j-1][k-1][0]):0;
}
}
t^=1;
}
printf("%d\n",add(f[t^1][m][K][0],f[t^1][m][K][1]));
return 0;
}
1892：【15NOIP提高组】运输计划
时间限制: 1000 ms 内存限制: 262144 KB
提交数: 614 通过数: 100
【题目描述】
公元2044年,人类进入了宇宙纪元。
L国有n个星球,还有n-1条双向航道,每条航道建立在两个星球之间,这n-1条航道连通了L国的所有星球。
小P掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从ui号星球沿最快的宇航路径飞行到vi号星球去。显然,飞船驶过一条航道是需要时间的,对于航道j,任意飞船驶过它所花费的时间为tj,并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新,L国国王同意小P的物流公司参与L国的航道建设,即允许小P把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小P的物流公司就预接了m个运输计划。在虫洞建设完成后, 这m个运输计划会同时开始,所有飞船一起出发。当这m个运输计划都完成时,小P的物流公司的阶段性工作就完成了。
如果小P可以*选择将哪一条航道改造成虫洞,试求出小P的物流公司完成阶段性工作所需要的最短时间是多少?
【输入】
第一行包括两个正整数 n、m,表示L国中星球的数量及小P公司预接的运输计划的数量,星球从1到n编号。
接下来n-1行描述航道的建设情况,其中第i行包含三个整数ai,bi和ti,表示第i条双向航道修建在ai与bi两个星球之间,任意飞船驶过它所花费的时间为ti。接下来m行描述运输计划的情况,其中第j行包含两个正整数uj和vj,表示第j个运输计划是从 uj号星球飞往vj号星球。
【输出】
共1行,包含1个整数,表示小P的物流公司完成阶段性工作所需要的最短时间。
【输入样例】
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
【输出样例】
11
【提示】
输入输出样例1说明：
将第1条航道改造成虫洞：则三个计划耗时分别为：11、12、11，故需要花费的时间为12。
将第2条航道改造成虫洞：则三个计划耗时分别为：7、15、11，故需要花费的时间为15。
将第3条航道改造成虫洞：则三个计划耗时分别为：4、8、11，故需要花费的时间为11。
将第4条航道改造成虫洞：则三个计划耗时分别为：11、15、5，故需要花费的时间为15。
将第5条航道改造成虫洞：则三个计划耗时分别为：11、10、6，故需要花费的时间为11。
故将第3条或第5条航道改造成虫洞均可使得完成阶段性工作耗时最短，需要花费的时间为11。
其它输入输出样例下载
所有测试数据的范围和特点如下表所示：
对于100%的数据，100≤n≤300000，1≤m≤300000100≤n≤300000，1≤m≤300000。
请注意常数因子带来的程序效率上的影响。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=300005;
int N,M,np=0,last[MAXN],dis[MAXN],dep[MAXN],size[MAXN],fa[MAXN],val[MAXN];
int dfs_clock=0,dfs_pos[MAXN],big_son[MAXN],top_node[MAXN];
int tot=0,root=0,lc[MAXN*2],rc[MAXN*2],MAX[MAXN*2],lazy[MAXN*2];
struct edge{int to,w,pre;}E[MAXN*2];
struct data{int l,r;};
data a[MAXN],k[MAXN];
bool cmp(data a,data b) {return a.l<b.l;}
char c;
void scan(int &x)
{
for(c=getchar();c<'0'||c>'9';c=getchar());
for(x=0;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
}
void addedge(int u,int v,int w)
{
E[++np]=(edge){v,w,last[u]};
last[u]=np;
}
void dfs1(int i)
{
for(int p=last[i];p;p=E[p].pre)
{
int j=E[p].to;
if(j==fa[i]) continue;
fa[j]=i;
dep[j]=dep[i]+1;
dis[j]=dis[i]+E[p].w;
size[j]=1;
val[j]=E[p].w;
dfs1(j);
size[i]+=size[j];
if(size[j]>size[big_son[i]]) big_son[i]=j;
}
}
void dfs2(int i,int top)
{
dfs_pos[i]=++dfs_clock;
top_node[i]=top;
if(!big_son[i]) return;
dfs2(big_son[i],top);
for(int p=last[i];p;p=E[p].pre)
{
int j=E[p].to;
if(j==fa[i]||j==big_son[i]) continue;
dfs2(j,j);
}
}
int LCA(int u,int v)
{
while(top_node[u]!=top_node[v])
{
if(dep[top_node[u]]<dep[top_node[v]]) swap(u,v);
u=fa[top_node[u]];
}
if(dep[u]>dep[v]) swap(u,v);
return u;
}
void build(int &now,int L,int R)
{
if(!now) now=++tot;
if(L==R) return;
int mid=(L+R)/2;
build(lc[now],L,mid);
build(rc[now],mid+1,R);
}
void pushup(int now) {MAX[now]=max(MAX[lc[now]],MAX[rc[now]]);}
void pushdown(int now)
{
if(!lazy[now]) return;
int l=lc[now],r=rc[now],w=lazy[now];
MAX[l]=max(MAX[l],w); lazy[l]=max(lazy[l],w);
MAX[r]=max(MAX[r],w); lazy[r]=max(lazy[r],w);
lazy[now]=0;
}
void update(int now,int L,int R,int i,int j,int w)
{
if(j<i) return;
if((i<=L)&&(R<=j))
{
MAX[now]=max(MAX[now],w);
lazy[now]=max(lazy[now],w);
return;
}
pushdown(now);
int mid=(L+R)/2;
if(i<=mid) update(lc[now],L,mid,i,j,w);
if(mid<j) update(rc[now],mid+1,R,i,j,w);
pushup(now);
}
int query(int now,int L,int R,int pos)
{
if(L==pos&&R==pos) return MAX[now];
pushdown(now);
int mid=(L+R)/2;
if(pos<=mid) return query(lc[now],L,mid,pos);
return query(rc[now],mid+1,R,pos);
}
void tree_up(int id,int w)
{
int u=a[id].l,v=a[id].r,cnt=0;
while(top_node[u]!=top_node[v])
{
if(dep[top_node[u]]<dep[top_node[v]]) swap(u,v);
k[++cnt]=(data){dfs_pos[top_node[u]],dfs_pos[u]};
u=fa[top_node[u]];
}
if(dep[u]>dep[v]) swap(u,v);
k[++cnt]=(data){dfs_pos[u]+1,dfs_pos[v]}; //注意同一条链上的节点，深度小的不能更新
sort(k+1,k+1+cnt,cmp);
if(k[1].l>1) update(root,1,N,1,k[1].l-1,w); //特判1，N
if(k[cnt].r<N) update(root,1,N,k[cnt].r+1,N,w);
for(int i=1;i<cnt;i++) update(root,1,N,k[i].r+1,k[i+1].l-1,w);
}
int ans(int id,int maxe)
{
int u=a[id].l,v=a[id].r,ans=2000000000,t;
if(u==v) return 0;
if(dep[u]<dep[v]) swap(u,v);
while(dep[u]!=dep[v])
{
ans=min(ans,max(maxe-val[u],t=query(root,1,N,dfs_pos[u])));
u=fa[u];
}
while(u!=v)
{
ans=min(ans,max(maxe-val[u],t=query(root,1,N,dfs_pos[u])));
ans=min(ans,max(maxe-val[v],t=query(root,1,N,dfs_pos[v])));
u=fa[u]; v=fa[v];
}
return ans;
}
int main()
{
int i,u,v,lca,w,s,maxe=0,maxid=0;
scan(N);scan(M);
for(i=1;i<N;i++)
{
scan(u);scan(v);scan(w);
addedge(u,v,w); addedge(v,u,w);
}
s=N/1; dfs1(s); dfs2(s,s); build(root,1,N);
for(i=1;i<=M;i++)
{
scan(u);scan(v);
if(dep[u]>dep[v]) swap(u,v);
a[i].l=u;
a[i].r=v;
lca=LCA(u,v);
w=dis[u]+dis[v]-2*dis[lca];
tree_up(i,w);
if(w>maxe)
{
maxe=w;
maxid=i;
}
}
cout<<ans(maxid,maxe);
return 0;
}
1893：【16NOIP提高组】玩具谜题
时间限制: 1000 ms 内存限制: 262144 KB
提交数: 1419 通过数: 674
【题目描述】
小南有一套可爱的玩具小人，它们各有不同的职业。有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图：
这时singer告诉小南一个谜题：“眼镜藏在我左数第3个玩具小人的右数第1个玩具小人的左数第2个玩具小人那里。”
小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。
小南一边艰难地辨认着玩具小人，一边数着：
“singer朝内，左数第3个是archer。
“archer朝外，右数第1个是thinker。
“thinker朝外，左数第2个是writer。
“所以眼镜藏在writer这里！”
虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为：
有n个玩具小入围成一圈，己知它们的职业和朝向。现在第1个玩具小人告诉小南一个包含m条指令的谜题，其中第i条指令形如“左数/右数第Si个玩具小人”。你需要输出依次数完这些指令后，到达的玩具小人的职业。
【输入】
输入的第一行包含两个正整数n，m，表示玩具小人的个数和指令的条数。
接下来n行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。其中0表示朝向圈内，1表示朝向圈外。保证不会出现其他的数。字符串长度不超过10且仅由小写字母构成，字符串不为空，并且字符串两两不同。整数和字符串之间用一个空格隔开。
接下来m行，其中第i行包含两个整数ai，Si，表示第i条指令。若ai=0，表示向左数Si个人；若ai=1，表示向右数Si个人。保证ai不会出现其他的数，1<si<n。
【输出】
输出一个字符串，表示从第一个读入的小人开始，依次数完m条指令后到达的小人的职业。
【输入样例】
7 3
0 singer
0 reader
0 mengbier
1 thinker
1 archer
0 writer
1 mogician
0 3
1 1
0 2
【输出样例】
writer
【提示】
【样例2输入】
10 10
1 c
0 r
0 p
1 d
1 e
1 m
1 t
1 y
1 u
0 v
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4
【样例2输出】
y
子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。
每个测试点的数据规模及特点如下表：
其中一些简写的列意义如下：
·全朝内：若为“√”，表示该测试点保证所有的玩具小人都朝向圈内；
·全左数：若为“√”，表示该测试点保证所有的指令都向左数，即对任意的 1<i<m, ai=0;
·Si=1：若为“√”，表示该测试点保证所有的指令都只数1个，即对任意的 1≤i≤m， Si=1；
·职业长度为1：若为“√”，表示该测试点保证所有玩具小人的职业一定是一个 长度为1的字符串。
#include<bits/stdc++.h>
using namespace std;
struct zz
{
int head ;
string name ;
} a[100000];
int n , m , ai , si ;
int main()
{
cin>>n>>m;
for(int i=0 ; i < n ; i++ )
{
cin>>a[i].head>>a[i].name;
}
int nowpos = 0 ;
for(int i=1;i<=m;i++)
{
scanf("%d%d" , &ai , &si );
if(a[nowpos].head == 0 && ai == 0)
nowpos = ( nowpos + n - si ) % n ;
else if( a[nowpos].head == 1 && ai == 1 )
nowpos = ( nowpos + n - si ) % n ;
else if( a[nowpos].head == 0 && ai == 1 )
nowpos = ( nowpos + si ) % n ;
else if( a[nowpos].head == 1 && ai == 0 )
nowpos = ( nowpos + si ) % n ;
}
cout<< a[nowpos].name << endl ;
return 0 ;
}
1894：【16NOIP提高组】天天爱跑步
时间限制: 2000 ms 内存限制: 524288 KB
提交数: 297 通过数: 138
【题目描述】
小C同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。
这个游戏的地图可以看作一棵包含nn个结点和n−1n−1条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从11到nn的连续正整数。
现在有mm个玩家，第ii个玩家的起点为SiSi，终点为TiTi。每天打卡任务开始时，所有玩家在第00秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）
小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。 在结点的观察员会选择在第WjWj秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第WjWj秒也理到达了结点JJ 。小C想知道每个观察员会观察到多少人?
注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一 段时间后再被观察员观察到。 即对于把结点JJ作为终点的玩家: 若他在第WjWj秒重到达终点,则在结点JJ的观察员不能观察到该玩家;若他正好在第WjWj秒到达终点,则在结点的观察员可以观察到这个玩家。
【输入】
第一行有两个整数nn和mm。其中nn代表树的结点数量，同时也是观察员的数量，mm代表玩家的数量。
接下来n−1n−1行每行两个整数uu和vv，表示结点uu到结点vv有一条边。
接下来一行nn个整数，其中第jj个整数为WjWj，表示结点jj出现观察员的时间。
接下来mm行,每行两个整数SiSi和TiTi，表示一个玩家的起点和终点。
对于所有的数据，保证1≤Si,Ti≤n，0≤Wj≤n1≤Si,Ti≤n，0≤Wj≤n。
【输出】
输出11行nn个整数,第jj个整数表示结点jj的观察员可以观察到多少人。
【输入样例】
6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6
【输出样例】
2 0 0 1 1 1
【提示】
【样例2输入】
5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5
【样例2输出】
1 2 1 0 1
对于1号点，W1=0，故只有起点为1号点的玩家才会被观察到，所以玩家1和玩家2被观察到，共2人被观察到。
对于2号点，没有玩家在第2秒时在此结点，共0人被观察到。
对于3号点，没有玩家在第5秒时在此结点，共0人被观察到。
对于4号点，玩家1被观察到，共1人被观察到。
对于5号点，玩家2被观察到，共1人被观察到。
对于6号点，玩家3被观察到，共1人被观察到。
测试点编号 nn mm 约定
11 =991=991 =991=991 所有人的起点等于自己的终点，即Si=TiSi=Ti
22
33 =992=992 =992=992 Wj=0Wj=0
44
55 =993=993 =993=993 无
66 =99994=99994 =99994=99994 树退化成一条链，其中11与22有边，
22与33有边，...，n−1n−1与nn有边
77
88
99 =99995=99995 =99995=99995 所有的Si=1Si=1
1010
1111
1212
1313 =99996=99996 =99996=99996 所有的Ti=1Ti=1
1414
1515
1616
1717 =99997=99997 =99997=99997 无
1818
1919
2020 =299998=299998 =299998=299998
如果你的程序需要用到较大的栈空间(这通常意味着需要较深层数的递归)，请务必仔细阅读选手目录下的文档running/stackpdf，以了解在最终评测时栈空间的限制与在当前工作环境下调整栈空间限制的方法。
#include <bits/stdc++.h>
using namespace std;
const int Add=300000;
const int Max=300005;
int n,m,s,tot;
int first[Max],dep[Max],top[Max],fa[Max],son[Max],size[Max];
int sum1[Max],sum2[Max<<1],w[Max],ans[Max];
vector<int> sum[Max][2],add[Max][2];
struct shu{int to,next;}edge[Max<<1];
inline int get_int()
{
int x=0,f=1;char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void print(int x)
{
if(x>9) print(x/10);
putchar('0'+x%10);
}
inline void build(int x,int y)
{
edge[++s].next=first[x],first[x]=s,edge[s].to=y;
}
void dfs1(int p)
{
size[p]=1;
for(int u=first[p];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa[p]) continue;
fa[to]=p,dep[to]=dep[p]+1,dfs1(to),size[p]+=size[to];
if(size[to]>size[son[p]]) son[p]=to;
}
}
void dfs2(int p,int tp)
{
top[p]=tp;
if(!son[p]) return;
dfs2(son[p],tp);
for(int u=first[p];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa[p]||to==son[p]) continue;
dfs2(to,to);
}
}
inline int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void dfs(int p)
{
int x1=w[p]+dep[p],x2=w[p]-dep[p],pre1=sum1[x1],pre2=sum2[x2+Add];
for(int u=first[p];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa[p]) continue;
dfs(to);
}
for(int i=0;i<sum[p][0].size();i++) sum1[sum[p][0][i]]+=add[p][0][i];
for(int i=0;i<sum[p][1].size();i++) sum2[sum[p][1][i]+Add]+=add[p][1][i];
ans[p]+=sum1[x1]-pre1,ans[p]+=sum2[x2+Add]-pre2;
}
int main()
{
n=get_int(),m=get_int();
for(int i=1;i<n;i++)
{
int x=get_int(),y=get_int();
build(x,y),build(y,x);
}
for(int i=1;i<=n;i++) w[i]=get_int();
dfs1(1),dfs2(1,1);
while(m--)
{
int x=get_int(),y=get_int(),f=LCA(x,y);
sum[x][0].push_back(dep[x]),add[x][0].push_back(1);
sum[y][1].push_back(dep[x]-2*dep[f]),add[y][1].push_back(1);
sum[f][0].push_back(dep[x]),add[f][0].push_back(-1);
sum[fa[f]][1].push_back(dep[x]-2*dep[f]),add[fa[f]][1].push_back(-1);
}
dfs(1);
for(int i=1;i<=n;i++) print(ans[i]),putchar(' ');
return 0;
}
1895：【16NOIP提高组】换教室
时间限制: 1000 ms 内存限制: 262144 KB
提交数: 354 通过数: 199
【题目描述】
对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。
在可以选择的课程中，有2n2n节课程安排在nn个时间段上。在第i(1<i<n)i(1<i<n)个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室cici上课，而另一节课程在教室didi进行。
在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的nn节安排好的课程。如果学生想更换第ii节课程的教室，则需要提出申请。若申请通过，学生就可以在第ii个时间段去教室didi上课，否则仍然在教室cici上课。
由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第ii节课程的教室时，申请被通过的概率是一个己知的实数kiki，并且对于不同课程的申请，被通过的概率是互相独立的。
学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多mm节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请;牛牛可以申请自己最希望更换教室的mm门课程，也可以不用完这mm个申请的机会，甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。
牛牛所在的大学有vv个教室，有ee条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。当第i(1≤i≤n−1)i(1≤i≤n−1)节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。
【输入】
第一行四个整数n,m,v,e.nn,m,v,e.n表示这个学期内的时间段的数量;mm表示牛牛最多可以申请更换多少节课程的教室;vv表示牛牛学校里教室的数量;ee表示牛牛的学校里道路的数量。
第二行nn个正整数，第i(1≤i≤n)i(1≤i≤n)个正整数表示cici，即第ii个时间段牛牛被安排上课的教室;保证1≤ci≤v1≤ci≤v。
第三行nn个正整数，第i(1≤i≤n)i(1≤i≤n)个正整数表示didi，即第ii个时间段另一间上同样课程的教室;保证1≤di≤v1≤di≤v。
第四行nn个实数，第i(1≤i≤n)i(1≤i≤n)个实数表示kiki，即牛牛申请在第ii个时间段更换教室获得通过的概率。保证0≤ki≤10≤ki≤1。
接下来ee行，每行三个正整数aj,bj,wjaj,bj,wj，表示有一条双向道路连接教室aj,bjaj,bj，通过这条道路需要耗费的体力值是WjWj;保证1≤aj,bj≤v,1≤wj≤10001≤aj,bj≤v,1≤wj≤1000
保证1≤n≤2000，0≤m≤2000，1≤v≤300，0≤e≤900001≤n≤2000，0≤m≤2000，1≤v≤300，0≤e≤90000。
保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。
保证输入的实数最多包含33位小数。
【输出】
输出一行，包含一个实数，四舍五入精确到小数点后恰好22位，表示答案。你的输出必须和标准输出完全一样才算正确。
测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于4×10−34×10−3(如果你不知道什么是浮点误差，这段话可以理解为:对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理)
【输入样例】
3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
【输出样例】
2.80
【提示】
【提示】
所有可行的申请方案和期望收益如下表
【样例2输入】
3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
【样例2输出】
2.80
【提示】
所有可行的申请方案和期望收益如下表
1.道路中可能会有多条双向道路连接相同的两间教室。也有可能有道路两端连接的是同一间教室。
2.请注意区分n,m,v,en,m,v,e的意义，nn不是教室的数量，mm不是道路的数量。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 2000
#define MAXV 300
int i,j,k,n,m,v,e,a,b,w;
int dist[MAXV+10][MAXV+10],c[MAXN+10],d[MAXN+10];
double P[MAXN+10],dp[MAXN+10][MAXN+10][2];
double ans = 2e9;
template <typename T> inline void read(T &x) {
int f=1; x=0;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template <typename T> inline void write(T x) {
if (x < 0) { putchar('-'); x = -x; }
if (x > 9) write(x/10);
putchar(x%10+'0');
}
template <typename T> inline void writeln(T x) {
write(x);
puts("");
}
int main() {
read(n); read(m); read(v); read(e);
for (i = 1; i <= v; i++) {
for (j = 1; j <= v; j++) {
if (i != j)
dist[i][j] = 2e9;
}
}
for (i = 1; i <= n; i++) read(c[i]);
for (i = 1; i <= n; i++) read(d[i]);
for (i = 1; i <= n; i++) cin >> P[i];
for (i = 1; i <= e; i++) {
read(a); read(b); read(w);
dist[a][b] = min(dist[a][b],w);
dist[b][a] = min(dist[b][a],w);
}
for (k = 1; k <= v; k++) {
for (i = 1; i <= v; i++) {
if (i == k) continue;
if (dist[i][k] == 2e9) continue;
for (j = 1; j <= v; j++) {
if (dist[k][j] == 2e9) continue;
if ((i == j) || (k == j)) continue;
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
for (i = 1; i <= n; i++) {
for (j = 0; j <= m; j++) {
dp[i][j][0] = dp[i][j][1] = 2e9;
}
}
dp[1][0][0] = 0; dp[1][1][1] = 0;
for (i = 2; i <= n; i++) {
dp[i][0][0] = dp[i-1][0][0] + dist[c[i-1]][c[i]];
for (j = 1; j <= min(i,m); j++) {
dp[i][j][0] = min(dp[i-1][j][0]+dist[c[i-1]][c[i]],dp[i-1][j][1]+dist[c[i-1]][c[i]]*(1.0-P[i-1])+dist[d[i-1]][c[i]]*P[i-1]);
dp[i][j][1] = min(dp[i-1][j-1][0]+dist[c[i-1]][d[i]]*P[i]*1.0+dist[c[i-1]][c[i]]*(1.0-P[i]),
dp[i-1][j-1][1]+
dist[d[i-1]][d[i]]*P[i-1]*P[i]*1.0+
dist[c[i-1]][d[i]]*(1.0-P[i-1])*P[i]+
dist[c[i-1]][c[i]]*(1.0-P[i-1])*(1.0-P[i])+
dist[d[i-1]][c[i]]*P[i-1]*(1-P[i])*1.0);
}
}
for (i = 0; i <= m; i++) ans = min(ans,min(dp[n][i][0],dp[n][i][1]));
cout<< fixed << setprecision(2) << ans << endl;
return 0;
}
1896：【16NOIP提高组】组合数问题
时间限制: 1000 ms 内存限制: 524288 KB
提交数: 770 通过数: 323
【题目描述】
组合数CmnCnm表示的是从nn个物品中选出mm个物品的方案数。举一个例子，从(1,2,3)(1,2,3)三个物品中选择两个物品可以有(1,2),(1,3),(2,3)(1,2),(1,3),(2,3)这三种选择方法。根据组合数的定义，我们可以给出组合数CmnCnm的一般公式：
Cmn=n!m!(n−m)Cnm=n!m!(n−m)
其中n!=1×2×...×nn!=1×2×...×n。
小葱想知道如果给定n,mn,m和kk，对于所有的0≤i≤n,0≤j≤min(i,m)0≤i≤n,0≤j≤min(i,m)有多少对(i,ji,j)满足cjicij是kk的倍数。
【输入】
第一行有两个整数t,kt,k，其中tt代表该测试点总共有多少组测试数据，kk的意义见【问题描述】。
接下来tt行每行两个整数n,mn,m，其中n,mn,m的意义见【问题描述】。
【输出】
tt行，每行一个整数代表所有的0<=i<=n,0<=j<=min(i,m)0<=i<=n,0<=j<=min(i,m)中有多少对(i,ji,j)满足C(j,i)C(j,i)是kk的倍数。
【输入样例】
1 2
3 3
【输出样例】
1
【提示】
【提示】
在所有可能的情况中，只有C(1,2)C(1,2)是22的倍数。
【样例2输入】
2 5
4 5
6 7
【样例2输出】
0
7
子任务
测试点 n m k t
1 ≤3 ≤3 =2 =1
2 =3 ≤104
3 ≤7 ≤7 =4 =1
4 =5 ≤104
5 ≤10 ≤10 =6 =1
6 =7 ≤104
7 ≤20 ≤100 =8 =1
8 =9 ≤104
9 ≤25 ≤2000 =10 =1
10 =11 ≤104
11 ≤60 ≤20 =12 =1
12 =13 ≤104
13 ≤100 ≤25 =14 =1
14 =15 ≤104
15 ≤60 =16 =1
16 =17 ≤104
17 ≤2000 ≤100 =18 =1
18 =19 ≤104
19 ≤2000 =20 =1
20 =21 ≤104
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2005
using namespace std;
int n,m,t,k;
int C[N][N],ans[N][N];
void init()
{
int i,j;
C[0][0]=1;
for(i=1;i<=2000;++i)
{
C[i][0]=1;
for(j=1;j<=i;++j)
{
C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
if(!C[i][j]) ans[i][j]++;
}
ans[i][i+1]=ans[i][i];
}
}
int main()
{
scanf("%d%d",&t,&k);
init();
while(t--)
{
scanf("%d%d",&n,&m);
printf("%d\n",m>n?ans[n][n]:ans[n][m]);
}
return 0;
}
1897：【16NOIP提高组】蚯蚓
时间限制: 1000 ms 内存限制: 524288 KB
提交数: 508 通过数: 174
【题目描述】
本题中，我们将用符号⌊c⌋⌊c⌋表示对cc向下取整，例如：⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。
蛐蛐国里现在共有nn只蚯蚓（nn为正整数）。每只蚯蚓拥有长度，我们设第ii只蚯蚓的长度为ai(i=1,2,...,n)ai(i=1,2,...,n)，并保证所有的长度都是非负整数（即：可能存在长度为00的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数pp（是满足0<p<p0<p<p的有理数）决定，设这只蚯蚓长度为xx ，神刀手会将其切成两只长度分别为⌊px⌋⌊px⌋ 和x−⌊px⌋x−⌊px⌋ 的蚯蚓。特殊地，如果这两个数的其中一个等于00，则这个长度为 00的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加qq（是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要mm秒才能到来 ……（mm为非负整数）
蛐蛐国王希望知道这mm秒内的战况。具体来说，他希望知道：
∙m∙m秒内，每一秒被切断的蚯蚓被切断前的长度（有mm个数）；
∙m∙m秒后，所有蚯蚓的长度（有n+mn+m个数）。
蛐蛐国王当然知道怎么做啦！但是他想考考你 ……
【输入】
第一行包含六个整数n，m，q，u，v，tn，m，q，u，v，t，其中：n，m，qn，m，q 的意义见「问题描述」；u，v，tu，v，t 均为正整数，你需要自己计算p=uvp=uv（保证0<u<v0<u<v ）；tt 是输出参数，其含义将会在「输出格式」中解释。
第二行包含nn个非负整数，为a1,a2,...,ana1,a2,...,an ，即初始时nn只蚯蚓的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。
保证1≤n≤105，0<m<7×106，0<u<v<109，0≤q≤200，1<t<71，0<ai<1081≤n≤105，0<m<7×106，0<u<v<109，0≤q≤200，1<t<71，0<ai<108。
【输出】
第一行输出⌊mt⌋个整数，按时间顺序，依次输出第⌊mt⌋个整数，按时间顺序，依次输出第t秒，第秒，第2t秒，第秒，第3t$ 秒 …… 被切断蚯蚓（在被切断前）的长度。
第二行输出⌊n+mt⌋⌊n+mt⌋个整数，输出mm秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第tt，第2t2t ，第 3t3t…… 的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。
请阅读样例来更好地理解这个格式。
【输入样例】
3 7 1 1 3 1
3 3 2
【输出样例】
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
【提示】
【提示】
在神刀手到来前:3只蚯蚓的长度为3,3,2。
1秒后:一只长度为3的蚯蚓被切成了两只长度分别为1和2的蚯蚓，其余蚯蚓的长度增加了1。最终4只蚯蚓的长度分别为((1,2),4,3。括号表示这个位置刚刚有一只蚯蚓被切断。
2秒后:一只长度为4的蚯蚓被切成了1和3 0 _5只蚯蚓的长度分别为:2,3,(1,3),4。
3秒后:一只长度为4的蚯蚓被切断。6只蚯蚓的长度分别为:3,4,2,4,(1,3)。
4秒后:一只长度为4的蚯蚓被切断。7只蚯蚓的长度分别为:4,(1,3),3,5,2,4。
5秒后:一只长度为_5的蛆叫被切断。8只蚯蚓的长度分别为:5,2,4,4,(1,4),3,5。
6秒后:一只长度为_5的蚯蚓被切断。9只蚯蚓的长度分别为:(1,4),3,5,5,2,5,4,6。
7秒后:一只长度为6的蚯蚓被切断。10只蚯蚓的长度分别为:2,5,4,6,6,3,6,5,(2,4)。
所以，7秒内被切断的蚯蚓的长度依次为3,4,4,4,5,5,60 7秒后，所有蚯蚓长度从大到小排序为6,6,6,5,5,4,4,3,2,2。
【样例2输入】
3 7 1 1 3 2
3 3 2
【样例2输出】
4 4 5
6 5 4 3 2
【提示2】
这个数据中只有t=2与上个数据不同。只需在每行都改为每两个数输出一个数即可 虽然第一行最后有一个6没有被输出，但是第二行仍然要重新从第二个数再开始输出
【样例3输入】
3 7 1 1 3 9
3 3 2
【样例3输出】
2
【提示3】
这个数据中只有t=9与上个数据不同。 注意第一行没有数要输出，但也要输出一个空行。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
int y[7200005],d[7200005],x[7200005],ly,ry,ld,rd,lx,rx,n,m,q,u,v,t,pl,bufpos;
long double p;
char buf[30000000];
inline void init(){
bufpos=0;
buf[fread(buf,1,30000000,stdin)]='\0';
}
inline int readint(){
int p=0;
for(;!isdigit(buf[bufpos]);bufpos++);
for(;isdigit(buf[bufpos]);bufpos++)
p=(p<<3)+(p<<1)+buf[bufpos]-'0';
return p;
}
bool com(int a,int b){return a>b;}
int main(){
init();
memset(y,129,sizeof y);
n=readint(),m=readint(),q=readint(),u=readint(),v=readint(),t=readint();
p=(long double)u/v;
for(int i=1;i<=n;++i)y[i]=readint();
sort(y+1,y+n+1,com);
ly=ld=lx=1;
ry=n;
rd=rx=pl=0;
memset(d,129,sizeof d);
memset(x,129,sizeof x);
for(int i=1;i<=m;++i){
int yb=y[ly]+pl,db=d[ld]+pl,xb=x[lx]+pl;
pl+=q;
if(db>xb){
if(db>yb){
if(i%t==0)printf("%d ",db);
int a=(int)(db*p);
int b=db-a;
if(a<b)swap(a,b);
d[++rd]=a-pl;
x[++rx]=b-pl;
++ld;
}else{
if(i%t==0)printf("%d ",yb);
int a=(int)(yb*p);
int b=yb-a;
if(a<b)swap(a,b);
d[++rd]=a-pl;
x[++rx]=b-pl;
++ly;
}
}else{
if(xb>yb){
if(i%t==0)printf("%d ",xb);
int a=(int)(xb*p);
int b=xb-a;
if(a<b)swap(a,b);
d[++rd]=a-pl;
x[++rx]=b-pl;
++lx;
}else{
if(i%t==0)printf("%d ",yb);
int a=(int)(yb*p);
int b=yb-a;
if(a<b)swap(a,b);
d[++rd]=a-pl;
x[++rx]=b-pl;
++ly;
}
}
}
printf("\n");
int ct=0;
while(ly<=ry||ld<=rd||lx<=rx){
++ct;
int yb=y[ly]+pl,db=d[ld]+pl,xb=x[lx]+pl;
if(db>xb){
if(db>yb){
if(ct%t==0)printf("%d ",db);
++ld;
}else{
if(ct%t==0)printf("%d ",yb);
++ly;
}
}else{
if(xb>yb){
if(ct%t==0)printf("%d ",xb);
++lx;
}else{
if(ct%t==0)printf("%d ",yb);
++ly;
}
}
}
printf("\n");
return 0;
}
1898：【16NOIP提高组】愤怒的小鸟
时间限制: 1000 ms 内存限制: 262144 KB
提交数: 500 通过数: 249
【题目描述】
Kiana最近沉迷于一款神奇的游戏无法自拔。
简单来说，这款游戏是在一个平面上进行的。
有一架弹弓位于(0,0)(0,0)处，每次Kiana可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如y=ax2+bxy=ax2+bx的曲线，其中a,ba,b是Kiana指定的参数，且必须满足a≤0a≤0。
当小鸟落回地面(即xx轴)时，它就会瞬间消失。
在游戏的某个关卡里，平面的第一象限中有nn只绿色的小猪，其中第ii只小猪所在的坐标为(xi,yi)(xi,yi)。
如果某只小鸟的飞行轨迹经过了(xi,yi)(xi,yi)，那么第ii只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行;
如果一只小鸟的飞行轨迹没有经过(xi,yi)(xi,yi)，那么这只小鸟飞行的全过程就不会对第ii只小猪产生任何影响。
例如，若两只小猪分别位于(1,31,3 )和(3,33,3 )
Kiana可以选择发射一只飞行轨迹为y=−x2+4xy=−x2+4x的小鸟，这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对Kiana来说都很难，所以Kiana还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。
假设这款游戏一共有TT个关卡，现在Kiana想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。
【输入】
第一行包含一个正整数TT，表示游戏的关卡总数。
下面依次输入这个TT个关卡的信息。每个关卡第一行包含两个非负整数n,mn,m，分别表示该关卡中的小猪数量和Kianna输入的神秘指令类型。接下来的nn行中，第ii行包含两个正实数xi,yixi,yi，表示第ii只小猪坐标为(xi,yi)(xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。
如果m=0m=0，表示Kianna输入了一个没有任何作用的指令。
如果m=1m=1，则这个关卡将会满足：至多用⌈n/3+1⌉⌈n/3+1⌉只小鸟即可消灭所有小猪。
如果m=2m=2，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少⌊n/3⌋⌊n/3⌋只小猪。
保证1≤n≤18,0≤m≤2，0<xi,yi<101≤n≤18,0≤m≤2，0<xi,yi<10，输入中的实数均保留到小数点后两位。
【输出】
对每个关卡依次输出一行答案。
输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。
【输入样例】
2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00
【输出样例】
1
1
【提示】
【提示1】
这组数据中一共有两个关卡。 第一个关卡与【问题描述】中的情形相同，22只小猪分别位于((1.00,3.00)(1.00,3.00)和(3.00,3.00)(3.00,3.00)，只需发射一只飞行轨迹为y=−x2+4xy=−x2+4x的小鸟即可消灭它们。 第二个关卡中有5只小猪，但经过观察我们可以发现它们的坐标都在抛物线y=−x2+6xy=−x2+6x上，故Kiana只需要发射一只小鸟即可消灭所有小猪。
【样例2输入】
3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00
【样例2输出】
2
2
3
【样例3输入】
1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99
【样例3输出】
6
【子任务】
数据的一些特殊规定如表：
测试点编号 nn mm TT
11 ≤2≤2 =0=0 ≤10≤10
22 ≤30≤30
33 ≤3≤3 ≤10≤10
44 ≤30≤30
55 ≤4≤4 ≤10≤10
66 ≤30≤30
77 ≤5≤5 ≤10≤10
88 ≤6≤6
99 ≤7≤7
1010 ≤8≤8
1111 ≤9≤9 ≤30≤30
1212 ≤10≤10
1313 ≤12≤12 =1=1
1414 =2=2
1515 ≤15≤15 =0=0 ≤15≤15
1616 =1=1
1717 =2=2
1818 ≤18≤18 =0=0 ≤5≤5
1919 =1=1
2020 =2=2
#include <bits/stdc++.h>
using namespace std;
const int Max=20;
int t,n,m;
int f[(1<<18)+10],g[Max][Max];
double x[Max],y[Max];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%lf%lf",&x[i],&y[i]);
memset(f,0x3f3f3f,sizeof(f)),memset(g,0,sizeof(g));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
if(i!=j)
{
double a=(y[i]/x[i]-y[j]/x[j])/(x[i]-x[j]);
double b=(x[i]/x[j]*y[j]-x[j]/x[i]*y[i])/(x[i]-x[j]);
if(a<=-1e-6)
for(int k=0;k<n;k++)
if(fabs(a*x[k]*x[k]+b*x[k]-y[k]) <= 1e-6) g[i][j]|=1<<k;
}
g[i][i]|=1<<i;
}
f[0]=0;
for(int i=0;i<(1<<n);i++)
for(int j=0;j<n;j++)
if(!((1<<j)&i))
{
for(int k=j;k<n;k++) if(!((1<<k)&i)) f[i|g[j][k]]=min(f[i|g[j][k]],f[i]+1);
break;
}
cout<<f[(1<<n)-1]<<"\n";
}
return 0;
}
1899：【17NOIP提高组】小凯的疑惑
时间限制: 1000 ms 内存限制: 262144 KB
提交数: 1469 通过数: 807
【题目描述】
小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。
【输入】
输入数据仅一行，包含两个正整数 aa 和 bb，它们之间用一个空格隔开，表示小凯手中金币的面值。
【输出】
输出文件仅一行，一个正整数 NN，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。
【输入样例】
3 7
【输出样例】
11
【提示】
【样例说明】
小凯手中有面值为33和77的金币无数个，在不找零的前提下无法准确支付价值为 1、2、4、5、8、111、2、4、5、8、11的物品，其中最贵的物品价值为1111。
比1111贵的物品都能买到，比如：
12=3×4+7×0
13=3×2+7×1
14=3×0+7×2
15=3×5+7×0
【数据范围】
对于 30% 的数据：1≤a,b≤501≤a,b≤50;
对于 60% 的数据： 1≤a,b≤10,0001≤a,b≤10,000;
对于 100% 的数据：1≤a,b≤1,000,000,0001≤a,b≤1,000,000,000。
样例数据下载
#include <bits/stdc++.h>
using namespace std;
long long n,m;
int main()
{
cin>>n>>m;
cout<<(n-1)*(m-1)-1<<"\n";
return 0;
}
1900：【17NOIP提高组】时间复杂度
时间限制: 1000 ms 内存限制: 262144 KB
提交数: 634 通过数: 276
【题目描述】
给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。 A++A++ 语言的循环结构如下：
F i x y
循环体
E
然后判断 ii 和 yy 的大小关系，若 ii 小于等于 yy 则进入循环，否则不进入。每次循环结束后 ii 都会被修改成 i+1i+1，一旦 ii 大于 yy 终止循环。 xx 和 yy 可以是正整数（xx 和 yy 的大小关系不定）或变量 nn。nn 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 100100。 EE表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。
注：本题中为了书写方便，在描述复杂度时，使用大写英文字母 OO 表示通常意义下 ΘΘ 的概念。
【输入】
第一行一个正整数 tt，表示有 t(t≤10)t(t≤10) 个程序需要计算时间复杂度。
每个程序我们只需抽取其中 FixyFixy和EE即可计算时间复杂度。注意：循环结构允许嵌套。
接下来每个程序的第一行包含一个正整数 LL 和一个字符串，LL 代表程序行数，字符串表示这个程序的复杂度，O(1)O(1)表示常数复杂度，O(nO(n^w)w) 表示复杂度为 nwnw ，其中 ww 是一个小于 100100 的正整数（输入中不包含引号），输入保证复杂度只有 O(1)O(1) 和 O(nO(n^w)w) 两种类型。
接下来 LL 行代表程序中循环结构中的 FixyFixy 或者 EE。 程序行若以 FF 开头，表示进入一个循环，之后有空格分离的三个字符（串）ixyixy，其中 ii 是一个小写字母（保证不为 nn ），表示新建的变量名，xx 和 yy 可能是正整数或 nn ，已知若为正整数则一定小于 100100。 程序行若以 EE开头，则表示循环体结束。
【输出】
输出共 tt 行，对应输入的 tt 个程序，每行输出YesYes或NoNo或者ERRERR，若程序实际复杂度与输入给出的复杂度一致则输出 YesYes，不一致则输出NoNo，若程序有语法错误（其中语法错误只有: ①FF 和 EE 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出ERRERR。
注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出ERRERR。
【输入样例】
8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E
【输出样例】
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR
【提示】
【样例说明】
第一个程序 ii 从11 到 11 是常数复杂度。
第二个程序 xx 从 11 到 nn 是 nn 的一次方的复杂度。
第三个程序有一个 FF 开启循环却没有E结束，语法错误。
第四个程序二重循环，nn 的平方的复杂度。
第五个程序两个一重循环，nn 的一次方的复杂度。
第六个程序第一重循环正常，但第二重循环开始即终止（因为 nn 远大于 100100，100100 大于 44）。
第七个程序第一重循环无法进入，故为常数复杂度。
第八个程序第二重循环中的变量 xx 与第一重循环中的变量重复，出现语法错误②，输出 ERRERR。
【数据范围】
对于 30% 的数据：不存在语法错误，数据保证小明给出的每个程序的前 L/2L/2 行一定为以 FF 开头的语句，第 L/2+1L/2+1 行至第 LL 行一定为以 EE 开头的语句，L≤10L≤10，若 xx,yy 均为整数，xx 一定小于 yy，且只有 yy 有可能为 nn。
对于 50% 的数据：不存在语法错误，L≤100L≤100，且若 xx,yy 均为整数，xx 一定小于 yy，且只有 yy 有可能为 nn。
对于 70% 的数据：不存在语法错误，L≤100L≤100。
对于 100% 的数据：t≤10,L≤100t≤10,L≤100。
样例数据下载
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<map>
#include<string>
using namespace std;
map<string,int>M;
map<int,string>used;
int t,l,tt,qw,t1,t2,flag,pd1,pd2,qww,l1,l2,ffl;
char ss[12],q1[20],q2[20],q3[20],q4[20];
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
scanf("%d",&l);scanf("%s",ss);
flag=0,tt=0,qw=0,pd1=0,pd2=0,qww=0,ffl=0;M.clear();used.clear();
if(ss[2]=='1')pd1=1;
else
{
pd2=ss[4]-'0';
if(ss[5]<='9'&&ss[5]>='0')
{
pd2=pd2*10+ss[5]-'0';
if(ss[6]<='9'&&ss[6]>='0')pd2=pd2*10+ss[6]-'0';
}
}
for(int j=1;j<=l;j++)
{
scanf("%s",q1);
if(q1[0]=='E')
{
if(!tt)
{
flag=1;
}
M[used[tt]]=0;
if(tt==ffl)ffl=0;
tt--;
qww=max(qww,qw);
if(qw)qw--;
//if(!tt)M.clear();
}else
{
tt++;
scanf("%s",q2);scanf("%s",q3);scanf("%s",q4);
if(M[q2])
{
flag=1;
}
used[tt]=q2;
M[used[tt]]=1;l1=strlen(q3);l2=strlen(q4);t1=0,t2=0;
for(int qq=0;qq<l1;qq++)t1=t1*10+q3[qq]-'0';
for(int qq=0;qq<l2;qq++)t2=t2*10+q4[qq]-'0';
if(((t1>t2)&&q4[0]!='n')||(q3[0]=='n'&&q4[0]!='n'))
{
if(!ffl)ffl=tt;
}else
{
if((q4[0]=='n')&&(!ffl)&&(q3[0]!='n'))qw++;
}
}
}
if(flag==1)
{
printf("ERR\n");continue;
}
if(tt)
{
printf("ERR\n");continue;
}
if(pd1&&!qww)
{
printf("Yes\n");continue;
}
if(qww==pd2)
{
printf("Yes\n");continue;
}
printf("No\n");
}
return 0;
}