@happyforever 2018-10-31T12:49:32.000000Z 字数 10327 阅读 523

10.28下午解题报告

清北学堂 解题报告

各题状况

期望得分： $50+30+50$
实际得分： $50+20+50$

题目及考场代码

T1

图片.png

/*
 * 拿上暴力分就跑
 * 真TM刺激
 * 吔
 */
#include <map>
#include <cstdio>
#include <string>
#include <iostream>
const int N=101,mod=1e9+7;
int n,len,ans;
std::string s,emp;
std::map<std::string,bool> mp;
void dfs(int now,int tot)
{
    if(now==n)
    {
        if(tot!=len)return ;
        int tot=0;
        for(int i=0;i<n;++i)
        {
            if(emp[i]=='(')
                ++tot;
            else
                if(tot)
                    --tot;
                else    return ;
        }
        if(!tot && !mp[emp])
        {
//          std::cout<<emp<<std::endl;
            mp[emp]=true;
            ++ans;
        }
        return ;
    }
    emp[now]='(';
    dfs(now+1,tot);
    emp[now]=')';
    dfs(now+1,tot);
    emp[now]=s[tot];
    dfs(now+1,tot+1);
}
int main()
{
    freopen("regular.in","r",stdin);
    freopen("regular.out","w",stdout);
    scanf("%d",&n);n<<=1;
    for(int i=0;i<n;++i)
        emp.push_back('*');
    std::cin>>s;
    len=s.size();
    dfs(0,0);
    printf("%d",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}

T2

图片.png

/*
 * 考虑记录读入的n个数，按从小到大排序之后看做数轴上的很多点
 * 考虑每次操作可以看做将数轴上一段区间变为一个点
 * 由于本题的各种操作时按顺序来的。。。。
 * 应该是相当于强制在线？
 * 反正不会
 * 可能是dp
 *
 * 吔
 */
#include <cstdio>
#include <algorithm>
const int inf=0x7f7f7f7f;
int n,m,ans=inf;
int num[1010];
struct Node{
    int l,r,x;
    bool operator<(const Node &gg)const
    {
        if(x==gg.x)
        {
            if(l==gg.l)
                return r<gg.r;
            return l<gg.l;
        }
        return x<gg.x;
    }
}v[100010],vv[10010];
inline int max(int x,int y)
{return x>y?x:y;}
inline int min(int x,int y)
{return x<y?x:y;}
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
/*
void dfs(int now,int step)
{
    if(now>m)
    {
        for(int i=2;i<=n;++i)
            if(a[i]!=a[i-1])
                return ;
        ans=min(ans,step);
        return ;
    }
    int l=work[now].l,r=work[now].r,x=work[now].x;
    for(int i=l;i<=r;++i)
        a[i]=x;
    dfs(now+1,step+1);
    for(int i=l;i<=r;++i)
        a[i]=i;
    dfs(now+1,step);
}
*/
bool judge(int tot)
{
    for(int i=1;i<=tot;++i)
        vv[i]=v[num[i]];
    for(int i=1;i<=tot;++i)
        for(int j=1;j<i;++j)
            if(vv[i].x>=vv[j].l&&vv[i].x<=v[j].r)
                vv[i].x==vv[j].x;
    std::sort(vv+1,vv+1+tot);
    int l=0,r=0;
    for(int i=1;i<=tot;++i)
    {
        if(vv[i].x!=vv[i-1].x)
        {
            if(l==1 && r==n)
                return true;
            l=vv[i].l;r=vv[i].r;
            continue;
        }
        if(vv[i].l<=r)  r=max(vv[i].r,r);
    }
    return l==1 && r==n;
}
void dfs(int now,int tot)
{
    if(now>m)
    {
        if(judge(tot))
            ans=min(ans,tot);
        return ;
    }
    num[tot+1]=now;
    dfs(now+1,tot+1);
    num[tot+1]=0;
    dfs(now+1,tot);
}
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        v[i]=(Node){read(),read(),read()};
    if(n<=10)
        dfs(1,0);
    printf("%d",ans==inf?-1:ans);
    fclose(stdin);fclose(stdout);
    return 0;
}

T3

图片.png

/*
 * 如果不是i~j而是i,j的话就是原题。
 * 问删掉某条边之后又多少连续区间在同一联通块内。
 * 
 * 只会暴力qwq
 */
#include<cstdio>
const int N=1001;
int n,head[N],ans,tot;
bool vis[N];
struct Edge{
    int v,nxt;
}edge[N<<1];
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
inline void add(int v,int u)
{
    edge[++tot]=(Edge){v,head[u]};head[u]=tot;
    edge[++tot]=(Edge){u,head[v]};head[v]=tot;
}
bool color,col[N];
void dfs(int now,int fa)
{
    col[now]=color;
    for(int v,i=head[now];i;i=edge[i].nxt)
        if((v=edge[i].v)!=fa)
            dfs(v,now);
}
void work()
{
    for(int i=1;i<=tot;++++i)
    {
//      printf("%d %d\n",edge[i].v,edge[i+1].v);
        color=false;
        col[edge[i+1].v]=false;
        for(int j=head[edge[i+1].v];j;j=edge[j].nxt)
            if(j!=i && j!=i+1)
                dfs(edge[j].v,edge[i+1].v);
        color=true;
        col[edge[i].v]=true;
        for(int j=head[edge[i].v];j;j=edge[j].nxt)
            if(j!=i && j!=i+1)
                dfs(edge[j].v,edge[i].v);
/*      
        for(int j=1;j<=n;++j)
            printf("%d ",col[j]?1:0);
        puts("");
*/
        for(int j=1;j<=n;++j)
            for(int k=j;col[j]==col[k] && k<=n;++k)
                ++ans;
    }
    printf("%d",ans);
}
int main()
{
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    n=read();
    for(int i=1;i<n;++i)
        add(read(),read());
    work();
    fclose(stdin); fclose(stdout);
    return 0;
}

正解及代码

原题中要求方案不重复，先考虑加的括号是红色的，原有的括号是黑色的
$dp[i][j][k]$ 表示现在用了 $i$ 个红括号， $j$ 个黑括号，左括号比右括号多 $k$ 个。
1. $k\gt 0$ 第 $j+1$ 个黑色括号是右括号
$dp[i][j][k]\rightarrow dp[i][j+1][k-1];$
2. $k\gt 0$ 第 $i+1$ 个红色括号是右括号
$dp[i][j][k]\rightarrow dp[i+1][j][k-1];$
3. 第 $j+1$ 个黑色括号是左括号
$dp[i][j][k]\rightarrow dp[i][j+1][k+1];$
4. 第 $i+1$ 个黑色括号是左括号
$dp[i][j][k]\rightarrow dp[i+1][j][k+1];$
$ans=dp[2n-m][m][0]$
但是对于原题不可行。

可 行 禁 止

$\begin{cases} dp[0][0][0]\rightarrow dp[0][1][1](可行)\\ dp[0][0][0]\rightarrow dp[1][0][1](禁止)\\ \end{cases}$
即：如果可以使用黑色，就优先使用黑色，这样方案不重不漏。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
//head
#define N 210
const int p=1000000007;
int n,m,s[N],ch[N][2],f[N],dp[N][N][N];
char str[N];
void add(int &a,int b){
    a+=b;
    if(p<=a)a-=p;
}
int main(){
    freopen("regular.in","r",stdin);
    freopen("regular.out","w",stdout);
    n=read();
    scanf("%s",str),m=strlen(str);
    dp[0][0][0]=1;
    rep(i,0,2*n-m)
        rep(j,0,m)
            rep(k,0,n)
                if(dp[i][j][k]){
                    if(j<m && str[j]=='(')add(dp[i][j+1][k+1],dp[i][j][k]);
                    else add(dp[i+1][j][k+1],dp[i][j][k]);
                    if(k>0){
                        if(j<m && str[j]==')')add(dp[i][j+1][k-1],dp[i][j][k]);
                        else add(dp[i+1][j][k-1],dp[i][j][k]);
                    }
                }
    cout<<dp[2*n-m][m][0]<<endl;
    return 0;
}

T2

图片.png
考虑题目实际是给了一些漏斗，要求选出最少的漏斗使得在 $1\sim n$ 任意位置扔都能漏到同一个位置
$40\%$ ：
首先离散化。“所有数字变为相同的数字”等价于“ $1$ 和 $n$ 变为相同的数字”。 $dp$ 记录行数，从第一列下落的目前所在列，从第 $n$ 列下落的目前所在列这三个量即可。复杂度是 $O(m^3)$
$60\%$ ：
可以发现上一个做法记录的后两个状态互不影响（在到最后一个漏斗之前两个位置是不相交不交错的），可以分别计算从 $1$ 经过前 $i$ 个操作变成j所需的最小花费数，对于n也类似这样做，找答案时只需枚举最后一个操作即可。复杂度 $O(m^2)$
$100%$ ：
在 $60\%$ 的解法基础上用线段树进行维护，时间复杂度 $O(m\log m)$

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
//head
const ll INF=(ll)1<<60;
#define N 110000
int n,m,a[N],b[N],c[N],q[N];
ll ans=INF;
struct seg{
    ll Min[N*4],a[N];
    void build(int u,int l,int r){
        if(l==r){
            Min[u]=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        Min[u]=min(Min[u*2],Min[u*2+1]);
    }
    ll find(int u,int l,int r,int x,int y){
        if(x<=l && y>=r)return Min[u];
        if(x>r || y<l)return INF;
        int mid=(l+r)>>1;
        return min(find(u*2,l,mid,x,y),find(u*2+1,mid+1,r,x,y));
    }
    void change(int u,int l,int r,int x,ll w){
        if(l==r){
            Min[u]=min(w,Min[u]);
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid)change(u*2,l,mid,x,w);
        else change(u*2+1,mid+1,r,x,w);
        Min[u]=min(Min[u*2],Min[u*2+1]);
    }
}t1,t2;
int bin1(int k){
    int l=1,r=q[0];
    while(l<r){
        int mid=(l+r)/2;
        if(q[mid]>=k)r=mid;
        else l=mid+1;
    }
    return l;
}
int bin2(int k){
    int l=1,r=q[0];
    while(l<r){
        int mid=(l+r)/2+1;
        if(k>=q[mid])l=mid;
        else r=mid-1;
    }
    return l;
}
int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    m=read();n=read();
    q[++q[0]]=1;
    q[++q[0]]=m;
    rep(i,1,n)a[i]=read(),b[i]=read(),c[i]=read(),q[++q[0]]=c[i];
    sort(q+1,q+q[0]+1);
    q[0]=1;
    rep(i,2,n+2)
        if(q[i]!=q[q[0]])q[++q[0]]=q[i];
    m=q[0];
    rep(i,1,q[0]){
        t1.a[i]=INF*(int)(i>1);
        t2.a[i]=INF*(int)(i<q[0]);
    }
    t1.build(1,1,q[0]);
    t2.build(1,1,q[0]);
    rep(i,1,n){
        a[i]=bin1(a[i]);
        b[i]=bin2(b[i]);
        c[i]=bin1(c[i]);
        ll f1=t1.find(1,1,q[0],a[i],b[i]),f2=t2.find(1,1,q[0],a[i],b[i]);
        ans=min(f1+f2+1,ans);
        t1.change(1,1,q[0],c[i],f1+1);
        t2.change(1,1,q[0],c[i],f2+1);
    }
    if(ans<INF)cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}

T3

set $+$ 启发式合并维护每棵子树内的编号，以 $01$ 表示是否在子树内，以 $L\sim R$ 的形式成段的记录在set中，每次修改一个位置时最多只需考虑set中相邻两个。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
//head
set<int>Q;
set<int>::iterator it,it1,it2;
#define N 210000
int head[N],v[N],fa[N],Next[N],k[N],f[N],s[N],son[N],siz[N],n,num,q[N],q2[N];
bool vis[N];
ll Ans,sum1,sum2;
void add(int x,int y){
    v[++num]=y;
    Next[num]=head[x];
    head[x]=num;
}
ll f1(ll x){return x*(x+1)/2;};
void dfs1(int u){
    int t=0,w=1;
    q[1]=u;
    while(t<w){
        int u=q[++t];
        siz[u]=1;
        for(int i=head[u];i;i=Next[i])
            if(v[i]!=fa[u]){
                fa[v[i]]=u;
                q[++w]=v[i];
            }
    }
    per(i,w,2){
        int u=q[i];
        siz[fa[u]]+=siz[u];
        if(siz[u]>siz[son[fa[u]]] || son[fa[u]]==0)son[fa[u]]=u;
    }
}
int find(int u){
    if(u==f[u])return u;
    return f[u]=find(f[u]);
}
void add(int u){
    k[u]=1;
    sum1++;
    if(k[u-1] && find(u-1)!=find(u)){
        int x=find(u-1),y=find(u);
        sum1+=1ll*s[x]*s[y];
        f[x]=y;
        s[y]+=s[x];
    }
    if(k[u+1] && find(u+1)!=find(u)){
        int x=find(u+1),y=find(u);
        sum1+=1ll*s[x]*s[y];
        f[x]=y;
        s[y]+=s[x];
    }
    Q.insert(u);
    it=Q.find(u);
    it1=it;
    it2=it;
    --it1;
    ++it2;
    sum2-=f1((*it2)-(*it1)-1);
    sum2+=f1((*it)-(*it1)-1);
    sum2+=f1((*it2)-(*it)-1);
}
void dfs3(int u){
    int t=0,w=1;
    q[1]=u;
    while(t<w){
        int u=q[++t];
        f[u]=u;s[u]=1;k[u]=0;
        for(int i=head[u];i;i=Next[i])
            if(v[i]!=fa[u])q[++w]=v[i];
    }
}
void dfs4(int u){
    int t=0,w=1;
    q[1]=u;
    while(t<w){
        int u=q[++t];
        add(u);
        for(int i=head[u];i;i=Next[i])
            if(v[i]!=fa[u])q[++w]=v[i];
    }
}
void clear(int u){
    Q.clear();
    Q.insert(0);
    Q.insert(n+1);
    sum1=0;
    sum2=f1(n);
    dfs3(u);
}
void dfs2(int u){
    int t=0,w=1;
    q2[1]=u;
    while(t<w){
        int u=q2[++t];vis[u]=0;
        for(int i=head[u];i;i=Next[i])
            if(v[i]!=fa[u])q2[++w]=v[i];
    }
    per(j,w,1)
        if(!vis[q2[j]]){
            int u=q2[j];
            while(!vis[u]){
                vis[u]=1;
                add(u);
                for(int i=head[u];i;i=Next[i])
                if(v[i]!=son[u] && v[i]!=fa[u])dfs4(v[i]);
                Ans+=f1(n)-sum1-sum2;
                if(fa[u]==0 || son[fa[u]]!=u)break;
                u=fa[u];
            }
            clear(u);
        }
}
int main(){
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    n=read();
    Q.clear();
    Q.insert(0);
    Q.insert(n+1);
    sum1=0;
    sum2=f1(n);
    rep(i,1,n)f[i]=i,s[i]=1,k[i]=0;
    rep(i,2,n){
        int x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dfs1(1);
    dfs2(1);
    cout<<f1(n)*(n-1)-Ans<<endl;
    return 0;
}

10.28下午解题报告

各题状况

题目及考场代码

T1

T2

T3

正解及代码

T2

T3

内容目录

选择主题