基本情况
前面过的很顺，F吃满罚时，T4次WA4次最后乱搞过的，K有一点思路，但是码力跟不上，其他没做的题题目基本没思路。
EF
https://ac.nowcoder.com/acm/contest/67742/E
https://ac.nowcoder.com/acm/contest/67742/F
两题虽然都是过了，但一个是提交前改了很久，一个是提交改了很久。
E
思路肯定没别的了，就是我的实现太容易出锅
-
\(\text{mycode}\)
void solve() { int n; cin >> n; vector<int> a(n); for (auto& i : a) cin >> i; if (n == 1) {cout << 1 << endl; return ;} if (count(all(a), 1) == 0 || count(all(a), 1) == n) { cout << n << endl; return ; } int del = 0; int pos = n - 1; while(pos > 0) { int last = pos; while(a[pos] == a[pos - 1] && pos > 0) pos--;//找到第一个和尾部不同的元素 if (pos == 0) {del += last - pos + 1; break;} del++; pos -= 2; if (pos == 0) {del++; break;} } cout << del << endl; }虽然最后过了，两个死亡
while而且这个pos -= 2看起来很不舒服，样例也是调了很久才过。 -
\(STD\)
while(T--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); ans=0; now=n;//这里多加了变量来维护尾部指针 for(i=n;i;i--) { if(a[i]!=a[now])//就不用像我那样判while套while，不容易出错 { ans++; now=i-1; } } for(i=1;i<=now;i++)//最后再找最后一段的答案。 { if(a[i]!=a[1]) break; ans++; } printf("%d\n",ans); }
F
想了三个解法，前两个超时但是正确性保证，第三个不超时但是部分错误。
最后用第三个解法加上分讨错误部分用第一个解法过了。
-
\(MyCode\)
void solve() { int n; cin >> n; vector<int> a(n); for (auto& i : a) cin >> i; if (n == 1) {cout << 1 << endl; return ;} set<int> color; vector<int> vis(n + 1); for (int i = 0; i < n; i++) color.insert(a[i]); int color_cmp = sz(color); int p = n - 1; ll ans = 0; int round = 0; int color_cnt = 0, last = 0; while(p > 0) {//大概思路就是找一段刚好达到总出现颜色数量的段，然后取该段最后一个（显然是改颜色的最右边出现的元素）直接删除。 round++; last = p; color_cnt = 0; while(p >= 0 && color_cnt < color_cmp) { if (vis[a[p]] < round) { vis[a[p]] = round; color_cnt++; } p--; } if (color_cnt == color_cmp) ans++; else {//但是这个算法对于最左边那段不适用 p = last; break; } if (p == 0) ans++; } if (p > 0) {//最后剩的一段，不知道怎么用上面方法是实现，就用了一开始比较暴力的方法。 stack<int> pos[n + 1]; color.clear(); for (int i = 0; i <= p; i++) color.insert(a[i]), pos[a[i]].push(i); while(p > 0) { int min_pos = inf; for (auto i : color) { while(!pos[i].empty() && pos[i].top() > p) pos[i].pop(); if (pos[i].empty()) continue; min_pos = min(min_pos, pos[i].top()); pos[i].pop(); } p = min_pos; ans++; } } cout << ans << endl; } -
\(STD\)
其实就类似于一开始比较暴力的方法，然后再用最后那个部分正确方法的思路优化，先把我一开始的方法贴上来吧
void solve() { int n; cin >> n; vector<int> a(n); for (auto& i : a) cin >> i; if (n == 1) {cout << 1 << endl; return ;} priority_queue<int, vector<int>, greater<int> > q; stack<int> pos[n + 1]; set<int> color; for (int i = 0; i < n; i++) { pos[a[i]].push(i); color.insert(a[i]); } int p = n - 1, ans = 0; while(p > 0) { int min_pos = inf; for (auto i : color) {//无脑把所有不符合的元素都出栈 while(!pos[i].empty() && pos[i].top() > p) pos[i].pop(); if (pos[i].empty()) continue; min_pos = min(min_pos, pos[i].top()); pos[i].pop(); } p = min_pos; ans++; } cout << ans << endl; }就是把每个颜色对应的每个位置入栈，然后每次出栈最栈顶靠前的颜色。
但是这里我每轮都进行了把位置在当前位置之后的元素都出栈的操作，会超时。
实际上可以通过类似我最后的方法，针对区间处理，每次删完元素就把处理区间转移到 \([找到新的元素的位置,这个元素左边]\)
void solve() { int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; stack<int> pos[n + 2]; for (int i = 1; i <= n; i++) pos[a[i]].push(i); int end_pos = n, ans = 0; for (int i = 1; i <= n; i++) if (!pos[i].empty()){ end_pos = min(end_pos, pos[i].top()); } int now = end_pos, pre = n;//now是当前要操作的颜色位置，pre是这个区间的右端 while(pre >= 1) { ans++; end_pos = now; for (int i = pre; i >= now; i--) {//把当前区间的颜色都出栈一次，因为操作的是now(end_pos)，显然它后面的元素都被删了 pos[a[i]].pop(); if (!pos[a[i]].empty()) end_pos = min(end_pos, pos[a[i]].top()); } pre = now - 1;//当前区间最右端变成了操作位置的左端，显然 now = end_pos; } cout << ans << endl; }
K
https://ac.nowcoder.com/acm/contest/67742/K
爆搜，我码力不够。
const int MAX=5e6+10;
const ll mod=1e9+7;
int n,used[12];
char a[MAX],b[MAX],to[12];
ll dfs(int x,int now,int ok)
{
if(x==n+1) return now==0;
if(a[x]>='0' && a[x]<='9')
{
if(!ok && a[x]>b[x]) return 0;
return dfs(x+1,(now*10+a[x]-'0')%8,ok|(a[x]<b[x]));
}
int i;
ll res=0;
if(a[x]>='a' && a[x]<='j')
{
if(to[a[x]-'a']!='#')
{
if(!ok && to[a[x]-'a']>b[x]) return 0;
return dfs(x+1,(now*10+to[a[x]-'a']-'0')%8,ok|(to[a[x]-'a']<b[x]));
}
else
{
for(i=((x==1&&n>1)?1:0);i<=9;i++)
{
if(used[i]) continue;
if(!ok && i>b[x]-'0') continue;
used[i]=1;
to[a[x]-'a']=i+'0';
res=(res+dfs(x+1,(now*10+i)%8,ok|(i<b[x]-'0')))%mod;
used[i]=0;
to[a[x]-'a']='#';
}
}
}
else if(a[x]=='_')
{
for(i=((x==1&&n>1)?1:0);i<=(ok?9:b[x]-'0');i++)
{
res=(res+dfs(x+1,(now*10+i)%8,ok|(i<b[x]-'0')))%mod;
}
}
return res;
}
int main()
{
int t,i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
scanf("%s",a+1);
scanf("%s",b+1);
memset(to,'#',sizeof to);
memset(used,0,sizeof used);
if(a[1]=='0')
{
if(n>1) puts("0");
else puts("1");
}
else printf("%lld\n",dfs(1,0,0));
}
return 0;
}
C
https://ac.nowcoder.com/acm/contest/67742/C
01字典树
GH
https://ac.nowcoder.com/acm/contest/67742/G
https://ac.nowcoder.com/acm/contest/67742/H
线段树及其进阶应用
D
标签：第二场,min,int,++,pos,牛客,训练赛,now,color From： https://www.cnblogs.com/kdlyh/p/18009528https://ac.nowcoder.com/acm/contest/67742/D
同余最短路