11.2日上午模拟测试总结

一.总体分析

考试满分 290

期望得分 100+100+78=278

实际得分 90+30+78=198

与自己理想的分数还是有距离，题目不难，有以下需要改进的地方

1.细节问题：第一题去重如果最后一个有重复，会多增加一个0,0点，WA掉一组数据。差点因为调试信息没去掉而WA。

　　一定要在模拟的地方处理好边界问题，调试信息一定要及时去掉

2.思维问题：第二题还是思维太局限，没有去认真想没有发现其中的规律

　　联赛时一种思路想不通了，可以换一种思路去想

3.技术问题：第三题卡递归我也是不想说什么了，其他地方都是板子，要注意求最长路的DP不要写挂了，可以直接写SPFA

二.题目分析

T1：同花顺

题目大意：给定n张扑克牌的花色和数字,问最少替换多少张牌,可以全部凑成同花顺?

思路分析：显然同花顺是同一个花色，那么先去重，排序，对于每一张牌i找到颜色一样，且数值<=wi的最后一张牌，计算之间牌的数量，即是不要变的数量。O(nlogn)

代码

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define inf (1<<30)
10 #define ll long long
11 #define RG register int
12 #define rep(i,a,b)    for(RG i=a;i<=b;i++)
13 #define per(i,a,b)    for(RG i=a;i>=b;i--)
14 #define maxn 100005
15 using namespace std;
16 int n,ans,cnt;
17 struct Dat{
18     int a,b;int dis;
19     inline bool operator < (const Dat &tmp)const{
20         return a==tmp.a?b<tmp.b:a<tmp.a;
21     }
22 }D[maxn];
23 set<Dat> st;
24 set<Dat>::iterator p,q;
25 
26 inline int read()
27 {
28     int x=0,f=1;char c=getchar();
29     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
30     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
31     return x*f;
32 }
33 void solve()
34 {        
35     ans=0;
36     for(q=st.begin();q!=st.end();++q)
37     {
38         p=st.lower_bound((Dat){(*q).a,(*q).b+n});
39         if(p==st.end())    {ans=max(ans,cnt-(*q).dis+1);continue;}
40         if((*p).a!=(*q).a)            ans=max(ans,(*p).dis-(*q).dis+1);
41         else if((*p).b>(*q).b+n)     ans=max(ans,(*p).dis-(*q).dis);
42         else                        ans=max(ans,(*p).dis-(*q).dis+1);
43     }
44     cout<<n-ans;
45 }
46 
47 int main()
48 {
49     freopen("card.in","r",stdin);
50     freopen("card.out","w",stdout);
51     n=read();
52     for(RG i=1,a,b;i<=n;i++)
53         D[i].a=read(),D[i].b=read();
54     sort(D+1,D+1+n);
55     int la=0,lb=0;
56     for(RG i=1;i<=n;i++)
57     {
58         while(D[i].a==la&&D[i].b==lb)    ++i;
59         la=D[i].a,lb=D[i].b;
60         st.insert((Dat){la,lb,++cnt});
61     }
62     solve();
63     return 0;
64 }

View Code

T2：做实验

题目大意：给定两个序列a[i]和b[i],问对于每个a[i],它的子集里面有多少不是a[i-b[i]]..a[i-1]的子集（a为b的子集的定义为数a的二进制中每一位为1都在b中出现）

思路分析：只要在区间a[i-b[i]]..a[i-1]出现了就对答案不能算做贡献，那么记录下f[i]为数i属于的最晚的一个集合。如果枚举出ai的每个子集j，如果f[j]<i-bi，那么就对答案作出共献。如何计算子集，tmp从a开始一直到1，每次tmp=a&(tmp-1)，相当于是舍去了那些不是子集的情况，且最大限度的保留了数字。（我就是这里没想到）

代码

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define inf (1<<30)
10 #define ll long long
11 #define RG register int
12 #define rep(i,a,b)    for(RG i=a;i<=b;i++)
13 #define per(i,a,b)    for(RG i=a;i>=b;i--)
14 #define maxn 100005
15 using namespace std;
16 int n,f[maxn],a,b,ans;
17 inline int read()
18 {
19     int x=0,f=1;char c=getchar();
20     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
21     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
22     return x*f;
23 }
24 
25 int main()
26 {
27     freopen("test.in","r",stdin);
28     freopen("test.out","w",stdout);
29     n=read();
30     rep(i,1,n)
31     {
32         a=read(),b=read();
33         int tmp=a;ans=0;
34         do{
35             if(f[tmp]<i-b)    ++ans;
36             f[tmp]=i;
37             tmp=a&(tmp-1);
38         }while(tmp);
39         printf("%d
",ans);
40     }
41     return 0;
42 }

View Code

T3：拯救世界

题目大意：给定一个有向图,每个点有一个权值。求从指定点到指定点,权值和最大的路径(可重复经过)

思路分析：很裸的SCC缩点后DP出最长路，但是SCC递归会被卡两个点，我也不知道怎么写飞递归的

代码（非AC）

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define inf (1<<30)
10 #define ll long long
11 #define RG register int
12 #define rep(i,a,b)    for(RG i=a;i<=b;++i)
13 #define per(i,a,b)    for(RG i=a;i>=b;--i)
14 #define maxn 500005
15 using namespace std;
16 int n,m,cnt,ct,K,S;
17 int id,sccn;
18 int h[maxn],head[maxn],val[maxn],f[maxn];
19 int dfn[maxn],low[maxn],scc[maxn];
20 bool ist[maxn],vis[maxn],tg[maxn];
21 stack<int> stk;
22 struct E{
23     int u,v,next;
24 }e[maxn];
25 struct EE{
26     int v,next;
27 }edge[maxn];
28 inline int read()
29 {
30     int x=0,f=1;char c=getchar();
31     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
32     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
33     return x*f;
34 }
35 
36 inline void add1(int u,int v)
37 {e[++cnt].v=v,e[cnt].u=u,e[cnt].next=h[u],h[u]=cnt;}
38 
39 inline void add2(int x,int y)
40 {edge[++ct].v=y,edge[ct].next=head[x],head[x]=ct;}
41 
42 void tarjan(int u)
43 {
44     dfn[u]=low[u]=++id;
45     vis[u]=tg[u]=1;
46     stk.push(u);
47     for(int i=h[u];i;i=e[i].next)
48     {
49         int v=e[i].v;
50         if(!dfn[v])
51         {
52             tarjan(v);low[u]=min(low[u],low[v]);
53         }
54         else if(vis[v])    low[u]=min(low[u],dfn[v]);
55     }
56     if(low[u]==dfn[u])
57     {
58         int tmp;sccn++;
59         do{
60             tmp=stk.top();stk.pop();
61             scc[tmp]=sccn,vis[tmp]=0;
62         }while(tmp!=u);
63     }
64 }
65 
66 void dfs(int u)
67 {
68     vis[u]=1;
69     for(int i=head[u];i;i=edge[i].next)
70     {
71         int v=edge[i].v;
72         if(!vis[v])    dfs(v);
73         f[u]=max(f[u],f[v]);
74     }
75     if(!f[u])    f[u]+=ist[u]?val[u]:0;
76     else        f[u]+=val[u];
77     return;
78 }
79 
80 int main()
81 {    
82     freopen("save.in","r",stdin);
83     freopen("save.out","w",stdout);
84     n=read(),m=read();
85     for(RG i=1,u,v;i<=m;++i)    {u=read(),v=read();add1(u,v);}
86     
87     rep(i,1,n)    if(!tg[i])    tarjan(i);
88     rep(i,1,n)    val[scc[i]]+=read();
89     S=read(),K=read();
90     for(RG i=1,tmp;i<=K;++i)    tmp=read(),ist[scc[tmp]]=1;
91     rep(i,1,cnt)    if(scc[e[i].u]!=scc[e[i].v])    add2(scc[e[i].u],scc[e[i].v]);
92     
93     memset(vis,0,sizeof(vis));
94     dfs(scc[S]);
95     cout<<f[scc[S]];
96     return 0;
97 }

View Code