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 }
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 }