10.3 考试总结
题面下载
得分情况
悲痛爆零
时间分配（大概）
8：30 $ \ $ -- $ \ $T1第一版dp写了出来，大样例没过，开始打dfs
9：20 $ \ $ -- $ \ $T1 dfs好像过了，感觉T3更简单，想去打T3
10：10 -- $ \ $T3把线段树分治打了一大部分突然卡住了，看T2
10：50 -- $ \ $没有看懂题意，以为f是一个序列的任意区域的mex，去看T4
11：00 -- $ \ $T4不会，回来优化T1
12：40 -- $ \ $T1突然出锅，没调出来，并把T3换成
错点
- T2题意理解有很大的问题，一直耗在那里
- T1，T3都是卡住了之后就换题了，想的有点少？
题目分析
匹配
考场思路
dfs(i,j)两个指针+记忆化
正解思路
跟考场思路一样。用dp做更简单。
code:
#include<bits/stdc++.h>
using namespace std;
string a,b;
int f[2021][2021];
int T,ans;
void solve(){memset(f,0,sizeof f);cin>>a>>b;int la=a.size(),lb=b.size();a=' '+a,b=' '+b;f[0][0]=1;for(int i=1;i<=la;i++){for(int j=1;j<=lb;j++){if('a'<=b[j] && b[j]<='z')if(a[i]==b[j]) f[i][j]=f[i][j] | f[i-1][j-1];if(b[j]=='.') f[i][j]=f[i][j] | f[i-1][j-1];if(b[j]=='*' && ((b[j-1]==a[i-1] && b[j-1]==a[i]) || (b[j-1]=='.' && a[i]==a[i-1]))) f[i][j]=f[i][j] | f[i-1][j];if(b[j]=='*') f[i][j]=f[i][j] | f[i][j-1];}}ans=0;for(int i=1;i<=la;i++) ans+=f[i][lb];cout<<ans<<'\n';
}
int main(){freopen("match.in","r",stdin);freopen("match.out","w",stdout);cin>>T;while(T--) solve();return 0;
}方阵
考场思路
题意都理解错了，那有什么思路
正解思路
因为w可以很大，而k又很小，所以考虑先将所有的数组按照w降序排序，依次计算ans。（排序+暴力+神经剪枝也能过）
code:
#include<bits/stdc++.h>
using namespace std;
inline int read() {int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return s*f;
}
const int N=2e4+5;
int n,ans;
int A[N];
struct node{int k,w,m;unsigned long long seed;unsigned long long _rand(){seed ^= seed << 13;seed ^= seed >> 7;seed ^= seed << 17;return seed;}
}a[N];
bool cmp1(node A,node B){if(A.w==B.w) return A.k>B.k;return A.w>B.w;
}
int cnt[N];
int get_pos(int u,int g){for(int i=0;i<=a[u].m;i++) cnt[i]=0;int pos=1,tmp=0;//pos表示当前右端点位置,tmp记录当前窗口内小于g的数的个数while(pos<=n){if(tmp==g) break;cnt[A[pos]]++;tmp+=(A[pos]<g && cnt[A[pos]]==1); pos++;}if(tmp<g) return 0;int last=1,res=n-pos+1,now=1;for(int i=++pos;i<=n;i++){cnt[A[i]]++;while(A[now]>=g || cnt[A[now]]-1>0) cnt[A[now]]--,now++;res+=(now-last)*(n-i+1);last=now;}return res;
}
int main(){freopen("mex.in","r",stdin);freopen("mex.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d%d%llu",&a[i].k,&a[i].w,&a[i].m,&a[i].seed);sort(a+1,a+n+1,cmp1);ans=a[1].w;for(int t=1;t<=n;t++){if(a[t].w+a[t].m>ans){for(int i=1;i<=n;i++)A[i]=a[t]._rand()%a[t].m;a[t].k=n*(n+1)/2-a[t].k;while(a[t].w+a[t].m>ans && get_pos(t,ans-a[t].w+1)>=a[t].k) ans++;}}cout<<ans;return 0;
}
合并
考场思路
正解思路
code:
数列
考场思路
正解思路
code: