noip模拟53 solutions
暴力分倒是拿得挺多，130pts，可是总是离正解就差那么一点点，然后就卡住了
不是我多么厉害，而是这个题的数据水，我错误的解法竟然可以拿到一半的分，比如T1
还是时间分配问题，这次落下了一个题，只是看了一眼，根本没有时间写
自信很重要，不要总是跟着别人的步伐，马上找到自己的节奏！！
T1 ZYB和售货机
呵呵，ZYB，好像是某个熟人，就是挂敌链的那小子。。。。。
就是让你求一个最大的收益，我们肯定是要让每一个商品都被收益最大的按钮按掉
我们找到每一个商品对应的收益最大的按钮，这样就连成了一个图
但是你发现一个问题：如果出现了环，那么环上必定有某一个点不能被它当前对应的按钮全部按掉，应该会剩下一个
原因就是如果你全按掉了，那么就会剩下一个商品按不掉了，因为你第一次全部按掉的商品的那个按钮已经不能按了
所以我们要拆除一条最大的边，换上一条次大的边，这样我们直接记录最大和次大就行了
一直跳最大的按钮，跳到一个环就换一个次大的
粘上我的32行代码
AC_code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
const int N=1e6+5;
const int inf=1e9;
int n,f[N],c[N],d[N],a[N],v[N];
int mx[N],nx[N],mn,bel[N],cnt;
ll ans;
void dfs(int x){
if(bel[x]==cnt){ans-=mn;return ;}
if(bel[x])return ;
bel[x]=cnt;
if(!mx[x])return ;
ans+=1ll*v[mx[x]]*a[x];
mn=min(mn,v[mx[x]]-v[nx[x]]);
if(mx[x]!=x)dfs(mx[x]);
}
signed main(){
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
scanf("%d",&n);
for(re i=1;i<=n;i++)scanf("%d%d%d%d",&f[i],&c[i],&d[i],&a[i]);
for(re i=1;i<=n;i++){
v[i]=d[f[i]]-c[i];
if(v[i]>=v[mx[f[i]]])nx[f[i]]=mx[f[i]],mx[f[i]]=i;
else if(v[i]>=v[nx[f[i]]])nx[f[i]]=i;
}
for(re i=1;i<=n;i++)if(!bel[i])mn=inf,++cnt,dfs(i);
printf("%lld",ans);
}
其实我考场上想的比较麻烦，我先把所有的物品全部平成1,这样不会有任何的影响
然后我就去跑最大生成树了，但是完全没有正确性，因为我只是保证了当前的最大
并没有保证全局加和是最大的，所以WA掉了
50pts
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
const int N=1e6+5;;
int n,f[N],c[N],d[N],a[N];
struct EDGE{
int fr,to,va;
EDGE(){}
EDGE(int x,int y,int z){fr=x;to=y;va=z;}
bool operator < (EDGE x)const{
return va>x.va;
}
}edg[N];
ll ans;
bool vis[N];
int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
signed main(){
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
scanf("%d",&n);
for(re i=1;i<=n;i++)scanf("%d%d%d%d",&f[i],&c[i],&d[i],&a[i]);
for(re i=1;i<=n;i++)edg[i]=EDGE(i,f[i],d[f[i]]-c[i]);
sort(edg+1,edg+n+1);
for(re i=1;i<=n;i++)if(edg[i].va>0)ans+=1ll*edg[i].va*(a[edg[i].to]-1),a[edg[i].to]=1;
for(re i=1;i<=n;i++)fa[i]=i;
for(re i=1;i<=n;i++){
if(edg[i].va<=0)break;
if(vis[edg[i].to])continue;
int x=find(edg[i].fr),y=find(edg[i].to);
if(x==y&&edg[i].fr!=edg[i].to)continue;
fa[x]=y;vis[edg[i].to]=true;
ans+=1ll*edg[i].va;
}
printf("%lld",ans);
}
T2 ZYB玩字符串
这个我是真的想不到\(DP\),所以直接上暴力了
看着像那种一点一点消掉的那种题，就是括号匹配。
所以我用了一个栈来存储当前匹配到哪里了，然后我发现好像有个地方处理不了
就是下一个字符你不知道是新开一个字符串还是接在原来的字符串上
所以我就用了一个\(dfs\),所以我下面的代码最快是\(mathcal{O(n^3)}\)最慢是\(mathcal{O(n^2×2^n)}\)
TLE 60pts
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=205;
int T,n,beg,en;
char s[N];
int ton[N][30];
stack<int> q;
bool dfs(int pos){
if(q.empty()){
if(pos==n+1)return true;
if(s[pos]!=s[beg])return false;
if(en-beg!=0)q.push(1);
return dfs(pos+1);
}
if(pos==n+1)return false;
bool fl1=false,fl2=false;
if(s[beg+q.top()]==s[pos]){
int tmp=q.top();q.pop();
if(tmp+1<en-beg+1)q.push(tmp+1);
fl1=dfs(pos+1);
if(tmp+1<en-beg+1)q.pop();
q.push(tmp);
}
if(s[beg]==s[pos]){
if(en-beg!=0)q.push(1);
fl2=dfs(pos+1);
if(en-beg!=0)q.pop();
}
return fl1||fl2;
}
signed main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%d",&T);
while(T--){
bool ok=false;
memset(ton,0,sizeof(ton));
scanf("%s",s+1);
n=strlen(s+1);
for(re i=1;i<=n;i++){
for(re j=0;j<=25;j++)
ton[i][j]=ton[i-1][j];
ton[i][s[i]-‘a‘]++;
}
for(re len=1;len<=n;len++){
if(n%len)continue;
for(re i=1;i+len-1<=n;i++){
int j=i+len-1;
if(s[i]!=s[1]||s[j]!=s[n])continue;
bool flag=false;
for(re k=0;k<=25;k++){
int tmp=ton[j][k]-ton[i-1][k];
if(!ton[n][k])continue;
if(!tmp){flag=true;break;}
if(ton[n][k]%tmp){flag=true;break;}
}
if(flag)continue;
while(!q.empty())q.pop();
//cout<<"sb"<<endl;
beg=i;en=j;
if(dfs(1)){
for(re k=i;k<=j;k++)printf("%c",s[k]);
printf("\n");
ok=true;break;
}
}
if(ok)break;
}
if(ok)continue;
}
}
就当我没有说上面的算法。。。。。。。
就按照题解上面说的打就行了，我只是在这里说一些减枝方法
首先，\(S\)的开头和末尾一定是\(p\)的开头和结尾
\(p\)的长度一定可以整除\(S\)的长度
统计字符个数，\(p\)的每一个字符的个数一定可以整除\(S\)的每一个字符的个数
可以用\(map+string\)的办法记录一下访问过的\(p\)，下次就不用他了
\(string\)千万不要直接赋值，建议用push_back或者直接转换
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=205;
int T,n;
char s[N];
int ton[N][30];
bool dp[N][N];
map<string,bool> mp;
signed main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%d",&T);
while(T--){
bool ok=false;mp.clear();
memset(ton,0,sizeof(ton));
scanf("%s",s+1);
n=strlen(s+1);
for(re i=1;i<=n;i++){
for(re j=0;j<=25;j++)
ton[i][j]=ton[i-1][j];
ton[i][s[i]-‘a‘]++;
}
for(re len=1;len<=n;len++){
if(n%len)continue;
for(re i=1;i+len-1<=n;i++){
int j=i+len-1;string c;
if(s[i]!=s[1]||s[j]!=s[n])continue;
bool flag=false;
for(re k=0;k<=25;k++){
int tmp=ton[j][k]-ton[i-1][k];
if(!ton[n][k])continue;
if(!tmp){flag=true;break;}
if(ton[n][k]%tmp){flag=true;break;}
}
if(flag)continue;
for(re k=i;k<=j;k++)c.push_back(s[k]);
if(mp.find(c)!=mp.end())continue;
mp.insert(make_pair(c,true));
memset(dp,false,sizeof(dp));
for(re k=1;k<=n;k++)dp[k][k]=(s[k]==s[i]);
for(re k=2;k<=n;k++){
for(re l=1;l+k-1<=n;l++){
int r=l+k-1;
dp[l][r]=(dp[l][r]||(dp[l][r-1]&&(s[r]==s[i+(r-l)%len])));
for(re o=1;o*len<=r-l+1;o++)dp[l][r]=(dp[l][r]||(dp[l][r-o*len]&&dp[r-o*len+1][r]));
}
}
if(dp[1][n]){
for(re k=i;k<=j;k++)printf("%c",s[k]);
printf("\n");
ok=true;break;
}
}
if(ok)break;
}
if(ok)continue;
}
}
T3 午餐
这个题确实是有点\(ex\)了，首先我看不出来这是最短路，第二看出来了也不会打。。。。
有一个贪心结论：在可行范围内，一定是越早学会越好
可行范围内就是说可以保证学不会的一直学不会，早的话就可以教给别人
首先我们要保证可行，所以我们定义数组\(low[i]\)表示，\(i\)节点最早啥时候可以学会
如果比这个再早一点的话，就会有一个\(-1\)的人学会了
你发现对于一条边来说，设我要用\(x\)去更新\(y\)，那么如果\(low[x]>R\)
说明\(low[x]\)不能通过当前对话学会，那么\(low[y]\)最早只能是\(L+1\),因为我留出来\(L\)用来对话
这样可以保证\(x\)学不会，如果\(low[x]\le R\)那么我就可以将对话安排在\(R\)这样对\(y\)就没有限制了，就是说可以让\(y\)去教\(x\)
那么我们有了这个最早啥时候能学会，这是一个限制，应该从\(-1\)的节点开始跑
让所有\(-1\)都学不会，所以这些\(-1\)的点的初始值都赋值为\(\infty\)
那要是我\(1\)节点也有限制，那就直接不合法就行了
下一次我们要求出来一个数组\(sui[i]\)表示，我啥时候可以学会，就是说我从\(1\)节点开始
就是如果比这个早的话，不能从\(1\)那边传过来
这个同样是最短路，我转移的时候直接在\(L,sui[x],low[y]\)之间取\(\max\)并且这个最大值要小于\(R\),不然就不能谈话了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,m,fi[N];
int sui[N],low[N];
struct EDGE{
int x,y,l,r;
EDGE(){}
}edg[N];
int to[N*2],nxt[N*2],val[N*2],var[N*2],head[N],rp;
void add_edg(int x,int y,int l,int r){
to[++rp]=y;
val[rp]=l;var[rp]=r;
nxt[rp]=head[x];
head[x]=rp;
}
struct node1{
int id,dis;
node1(){}
node1(int x,int y){id=x;dis=y;}
bool operator < (node1 x)const{
return dis<x.dis;
}
};
priority_queue<node1> q1;
struct node2{
int id,dis;
node2(){}
node2(int x,int y){id=x;dis=y;}
bool operator < (node2 x)const{
return dis>x.dis;
}
};
priority_queue<node2> q2;
signed main(){
freopen("lunch.in","r",stdin);
freopen("lunch.out","w",stdout);
scanf("%d%d",&n,&m);
for(re i=1;i<=m;i++){
scanf("%d%d%d%d",&edg[i].x,&edg[i].y,&edg[i].l,&edg[i].r);
add_edg(edg[i].x,edg[i].y,edg[i].l,edg[i].r);
add_edg(edg[i].y,edg[i].x,edg[i].l,edg[i].r);
}
for(re i=1;i<=n;i++)scanf("%d",&fi[i]);
for(re i=1;i<=n;i++)if(fi[i]==-1)low[i]=inf,q1.push(node1(i,inf));
while(!q1.empty()){
int x=q1.top().id,dis=q1.top().dis;q1.pop();
//cout<<dis<<" ";
for(re i=head[x];i;i=nxt[i]){
int y=to[i];
if(dis>var[i]&&val[i]+1>low[y]){
low[y]=val[i]+1;q1.push(node1(y,low[y]));
}
}
}
//cout<<endl;
//for(re i=1;i<=n;i++)cout<<low[i]<<" ";
//cout<<endl;
if(low[1]){printf("Impossible");return 0;}
memset(sui,0x3f,sizeof(sui));sui[1]=0;q2.push(node2(1,0));
while(!q2.empty()){
int x=q2.top().id,dis=q2.top().dis;q2.pop();
//cout<<dis<<" ";
for(re i=head[x];i;i=nxt[i]){
int y=to[i];
int mx=max(val[i],max(dis,low[y]));
if(mx<sui[y]&&mx<=var[i])sui[y]=mx,q2.push(node2(y,sui[y]));
}
}
//cout<<endl;
for(re i=1;i<=n;i++)if(fi[i]==1&&sui[i]==inf){printf("Impossible");return 0;}
for(re i=head[1];i;i=nxt[i])if(fi[to[i]]==-1){printf("Impossible");return 0;}
for(re i=1;i<=m;i++){printf("%d\n",max(sui[edg[i].x],sui[edg[i].y])>edg[i].r?edg[i].l:max(edg[i].l,max(sui[edg[i].x],sui[edg[i].y])));}
}
T4 计数
基础dp极其简单，直接枚举左右子树的大小就行了
然后去观察这个限制，哎呀就直接看官方的吧，写得非常明白了
保证\(a\lt b\)，那么限制就是中序遍历中\(a\gt b\)或者\(a\lt b\)
我们然后找规律就行了，一个是大于啥，一个是小于啥
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=405;
const int M=1e3+5;
const int mod=1e9+7;
int T,n,m;
int u[M],v[M];
int f[N][N],ans;
int lim[N][2];
int dfs(int x,int sz){
if(f[x][sz]!=-1)return f[x][sz];
if(sz==0)return 1;
f[x][sz]=0;
for(re i=max(0,lim[x][0]);i<=min(sz-1,lim[x][1]);i++){
f[x][sz]=(f[x][sz]+1ll*dfs(x+1,i)*dfs(x+i+1,sz-1-i))%mod;
}
return f[x][sz]%mod;
}
signed main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(f,-1,sizeof(f));
for(re i=1;i<=n;i++)lim[i][0]=0,lim[i][1]=n-i+1;
for(re i=1;i<=m;i++){
scanf("%d%d",&u[i],&v[i]);
if(u[i]<v[i])lim[u[i]][1]=min(lim[u[i]][1],v[i]-u[i]-1);
else lim[v[i]][0]=max(lim[v[i]][0],u[i]-v[i]);
}
printf("%d\n",dfs(1,n));
}
}