2017-10-23 NOIP模拟赛
阅读原文时间:2023年07月10日阅读:2

题目描述

现在有一个字符串,每个字母出现的次数均为偶数。接下来我们把第一次出现的字母a和第二次出现的a连一条线,第三次出现的和四次出现的字母a连一条线,第五次出现的和六次出现的字母a连一条线…对其他25个字母也做同样的操作。

现在我们想知道有多少对连线交叉。交叉的定义为一个连线的端点在另外一个连线的内部,另外一个端点在外部。

下图是一个例子,共有三对连线交叉(我们连线的时候,只能从字符串上方经过)。

输入格式

一行一个字符串。保证字符串均由小写字母组成,且每个字母出现次数为偶数次。

输出格式

一个整数,表示答案。

样例输入

abaazooabz

样例输出

3

数据范围

对于30% 的数据,字符串长度不超过50。

对于100% 的数据,字符串长度不超过100,000。

#include
#include
#include
using namespace std;
int top,ans,cnt[],pos[],num[],a[];
char s[];
int main(){
freopen("cross.in","r",stdin);freopen("cross.out","w",stdout);
//freopen("Cola.txt","r",stdin);
scanf("%s",s);
int len=strlen(s);
memset(pos,0x3f,sizeof(pos));
for(int i=;i<len;i++){
int now=s[i]-'a';
num[now]++;
if(num[now]%==){
ans+=cnt[now];
for(int j=;j<;j++){
if(j==now)continue;
if(pos[j]<pos[now])cnt[j]--;
}
pos[now]=0x7fffffff;
cnt[pos[now]]=;
}
else {
a[top]=now;
pos[now]=top;
cnt[now]=;
top++;
for(int j=;j<;j++){
if(j==now)continue;
if(pos[j]<pos[now])cnt[j]++;
}
}
}
printf("%d",ans);
}

100分 栈模拟

#include
#include
#include
#include
#include
#define maxn 501
using namespace std;
int n,m,p,k,num,head[maxn],f[][];
struct node{int to,pre,v,mark;}e[+];
struct Node{
int id,cnt,dis;
bool operator < (const Node b)const{ return dis>b.dis;
}
};
Node make_Node(int id,int cnt,int dis){
Node res;
res.id=id;res.cnt=cnt;res.dis=dis;
return res;
}
void Insert(int from,int to,int v,int mark){
e[++num].to=to;
e[num].v=v;
e[num].mark=mark;
e[num].pre=head[from];
head[from]=num;
}
priority_queueq;
void Dij(){
q.push(make_Node(,,));
memset(f,0x3f,sizeof(f));f[][]=;
while(!q.empty()){
Node now=q.top();int point=now.id,d=now.dis,c=now.cnt;
q.pop();
for(int i=head[point];i;i=e[i].pre){
int to=e[i].to;
if(e[i].mark==&&f[to][c]>f[point][c]+e[i].v){
f[to][c]=f[point][c]+e[i].v;
q.push(make_Node(to,c,f[to][c]));
}
if(cf[point][c]+e[i].v){
f[to][c+]=f[point][c]+e[i].v;
q.push(make_Node(to,c+,f[to][c+]));
}
}
}
}
int main(){
//freopen("Cola.in","r",stdin);
freopen("move.in","r",stdin);freopen("move.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&p,&k);
int x,y,z;
for(int i=;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,); } for(int i=;i<=p;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,); } Dij(); int ans=0x7fffffff; for(int i=;i<=min(k,p);i++){ ans=min(ans,f[n][i]); } if(ans>){puts("-1");return ;}
printf("%d",ans);
}

80分 Dij+dp

#include
#include
#include
#include
#define maxn 5010
using namespace std;
int n,m,p,k,l,r,mid;
int num,head[maxn],num2,head2[maxn],dis[maxn];
bool vis[maxn],ok[maxn],flag;
struct node{
int to,pre,v,mark;
}e[maxn],e2[maxn];
void Insert(int from,int to,int v,int mark){
e[++num].to=to;
e[num].v=v;
e[num].pre=head[from];
e[num].mark=mark;
head[from]=num;
}
void Insert2(int from,int to,int v,int mark){
e2[++num2].to=to;
e2[num2].v=v;
e2[num2].pre=head2[from];
e2[num2].mark=mark;
head2[from]=num2;
}
void Spfa(){
queueq;
memset(dis,0x3f,sizeof(dis));
memset(vis,,sizeof(vis));
vis[]=;dis[]=;
q.push();
while(!q.empty()){
int now=q.front();q.pop();vis[now]=;
for(int i=head[now];i;i=e[i].pre){
if(e[i].mark)continue;
int to=e[i].to;
if(dis[to]>dis[now]+e[i].v){
dis[to]=dis[now]+e[i].v;
if(!vis[to])vis[to]=,q.push(to);
}
}
}
}
void dfs(int now,int d,int t){
if(t>k)return;
if(d>mid)return;
if(now==n){flag=;return;}
if(flag)return;
for(int i=head[now];i;i=e[i].pre){
int to=e[i].to;
if(!ok[to])continue;
if(!vis[to]){
vis[to]=;
dfs(to,d+e[i].v,t+e[i].mark);
vis[to]=;
}
}
}
bool check(){
flag=;
memset(vis,,sizeof(vis));
vis[]=;
dfs(,,);
if(flag)return ;
else return ;
}
void bfs(){
queueq;
q.push(n);ok[n]=;
while(!q.empty()){
int now=q.front();q.pop();
for(int i=head2[now];i;i=e2[i].pre){
int to=e2[i].to;
if(!ok[to]){
ok[to]=;
q.push(to);
}
}
}
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("move.in","r",stdin);freopen("move.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&p,&k);
int x,y,z;
for(int i=;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,); Insert2(y,x,z,); r+=z; } for(int j=;j<=p;j++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,); Insert2(y,x,z,); r+=z; } if(k==){ Spfa(); if(dis[n]>=){puts("-1");return ;}
printf("%d",dis[n]);return ;
}
else {
bfs();
if(!ok[]){puts("-1");return ;}
int ans=-;
while(l<=r){ mid=(l+r)>>;
if(check())ans=mid,r=mid-;
else l=mid+;
}
printf("%d",ans);
}
}

95分 二分答案

#include
#include
#include
#include
#include
#define maxn 501
using namespace std;
int n,m,p,k,num,head[maxn],f[][];
bool vis[maxn][];
struct node{int to,pre,v,mark;}e[+];
struct Node{
int id,cnt,dis;
bool operator < (const Node b)const{ return dis>b.dis;
}
};
Node make_Node(int id,int cnt,int dis){
Node res;
res.id=id;res.cnt=cnt;res.dis=dis;
return res;
}
void Insert(int from,int to,int v,int mark){
e[++num].to=to;
e[num].v=v;
e[num].mark=mark;
e[num].pre=head[from];
head[from]=num;
}
priority_queueq;
void Dij(){
q.push(make_Node(,,));
memset(f,0x3f,sizeof(f));f[][]=;
while(!q.empty()){
Node now=q.top();int point=now.id,d=now.dis,c=now.cnt;
if(point==n)break;//非常有用的一句话
q.pop();
for(int i=head[point];i;i=e[i].pre){
int to=e[i].to;
if(e[i].mark==&&f[to][c]>f[point][c]+e[i].v){
f[to][c]=f[point][c]+e[i].v;
q.push(make_Node(to,c,f[to][c]));
}
if(cf[point][c]+e[i].v){
f[to][c+]=f[point][c]+e[i].v;
q.push(make_Node(to,c+,f[to][c+]));
}
}
}
}
int main(){
//freopen("Cola.in","r",stdin);
freopen("move.in","r",stdin);freopen("move.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&p,&k);
int x,y,z;
for(int i=;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,); } for(int i=;i<=p;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,); } Dij(); int ans=0x7fffffff; for(int i=;i<=min(k,p);i++){ ans=min(ans,f[n][i]); } if(ans>){puts("-1");return ;}
printf("%d",ans);
}

100分 Dij+dp(一个有用的优化)

#include
#include
#include
#include
#define maxn 5010
#define mod 786433
using namespace std;
int n,k,num,head[maxn],fal[maxn],sz[maxn],ans,can[maxn],c;
bool vis[maxn],v[maxn];
struct node{
int to,pre,v;
}e[maxn];
void Insert(int from,int to,int id){
e[id].to=to;
e[id].pre=head[from];
head[from]=id;
num=max(num,id);
}
void Dfs(int now,int father){
sz[now]=;
for(int i=head[now];i;i=e[i].pre){
int to=e[i].to;
if(to==father)continue;
fal[to]=i;
Dfs(to,now);
sz[now]+=sz[to];
}
}
int bfs(int x){
int res=;
queueq;
q.push(x);
vis[x]=;
while(!q.empty()){
int now=q.front();q.pop();
for(int i=head[now];i;i=e[i].pre){
if(e[i].v!=)continue;
int to=e[i].to;
if(!vis[to]){
vis[to]=;
q.push(to);
res++;
}
}
}
return res;
}
bool check(){
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++){ if(!vis[i]){ if(bfs(i)c){
//for(int i=1;i<=num;i++)cout<=mod)ans-=mod;
}
return;
}
dfs(pos+);
int w=(can[pos]>=n?(can[pos]-n+):(can[pos]+n-));
e[can[pos]].v=;
e[w].v=;
dfs(pos+);
e[can[pos]].v=;
e[w].v=;
}
int main(){
//freopen("Cola.in","r",stdin);
freopen("cut.in","r",stdin);freopen("cut.out","w",stdout);
scanf("%d%d",&n,&k);
int x,y;
for(int i=;i=n?fal[i]-n+:fal[i]+n-);
//e[w].v=1;
v[fal[i]]=v[w]=;
sum++;
}
for(int i=;i<=num;i++){ if(v[i]==){ can[++c]=i; int w=(i>=n?i-n+:i+n-);
v[w]=;
v[i]=;
}
}
dfs();
printf("%d",ans);
return ;
}

20分 暴力

#include
#include
#define N 5555
#define M 786433
using namespace std;
typedef long long LL;
struct edge
{
int t,n;
}e[N*];
LL h[N],size[N],f[N][N],g[N],cnt[N];
int n,K,tote;
void add(int u,int v)
{
e[++tote].t=v;
e[tote].n=h[u];
h[u]=tote;
return ;
}
void dfs(int u,int fa)
{
size[u]++; f[u][]=;
for (int i=h[u];i;i=e[i].n)
{
int v=e[i].t;
if (v==fa) continue;
dfs(v,u);
for (int j=;j<=size[u]+size[v];j++) g[j]=;
for (int j=;j<=size[u];j++) g[j]=cnt[v]*f[u][j]%M;
for (int j=;j<=size[u];j++)
for (int k=;k<=size[v];k++) g[j+k]=(g[j+k]+f[u][j]*f[v][k]%M)%M;
for (int j=;j<=size[u]+size[v];j++) f[u][j]=g[j];
size[u]+=size[v];
}
for (int i=K;i<=size[u];i++) cnt[u]=(cnt[u]+f[u][i])%M;
return ;
}
int main()
{
freopen("cut.in","r",stdin);
freopen("cut.out","w",stdout);
scanf("%d %d",&n,&K);
for (int i=;i<n;i++)
{
int u,v;
scanf("%d %d",&u,&v);
add(u,v); add(v,u);
}
dfs(,);
printf("%d\n",cnt[]);
fclose(stdin);
fclose(stdout);
return ;
}

100分 树形背包