A. 语言
想到小学英语老师一遍遍地强调：每个句子有且只有一个动词！！忽然给了我灵感。发现不是动词的部分AN可以自由组合，A可以这样连续A(AN)，A(A(AN))，唯一不合法的情况就是A在末尾，也就是V分出来的前后两段中末尾只要有可能是N就Yes，判断一下就好了。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 3;
char s[maxn];
int T, n, zm[30], cnt, pos;
bool flag;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
freopen("language.in", "r", stdin);
freopen("language.out", "w", stdout);
T = read();
while(T--)
{
for(int i=1; i<=26; i++)
{
zm[i] = read();
}
flag = 0; cnt = 0; pos = 0;
scanf("%s", s+1); n = strlen(s+1);
if(!(zm[s[n]-'a'+1] & 2))
{
printf("No\n"); continue;
}
for(int i=1; i<=n; i++)
{
if(zm[s[i]-'a'+1] == 4) cnt++, pos = i;
}
if(cnt > 1 || pos == 1)
{
printf("No\n"); continue;
}
if(pos)
{
if(zm[s[pos-1]-'a'+1] & 4) printf("Yes\n");
else printf("No\n");
}
else
{
for(int i=2; i<n; i++)
{
if((zm[s[i]-'a'+1] & 4) && (zm[s[i-1]-'a'+1] & 2))
{
flag = 1; printf("Yes\n"); break;
}
}
if(!flag) printf("No\n");
}
}
return 0;
}
B. 色球
->思考怎么写链表遇到了两个问题： 1.每一个链表大小开maxn，有maxn个位置，会MLE sol：链表占用的内存和是maxn，链表结构体只需要一个，其实这个和邻接链表存图很相似 2.链表分为pre和nxt，一会走pre一会走nxt判断起来太复杂 sol：双向链表都是中间pre和nxt都满着，两边空一个，用满的填空的来合并，从端点开始找满的那个是单向的 process： 无限容器，盲猜vector都会炸，所以搞了个什么回退把空间复杂度降到了O(n)，结果还不如写个暴力呢。。 我居然都没有写个暴力保底。。考试策略差评code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 3;
int n, m, ans;
typedef pair<int, int> pii;
vector<pii> ve[maxn];
char op[7];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
freopen("color.in", "r", stdin);
freopen("color.out", "w", stdout);
n = read(); m = read();
while(m--)
{
scanf("%s", op);
if(op[2] == 's')
{
int x = read(), y = read(), z = read();
ve[z].push_back(pii(x, y));
}
else if(op[2] == 't')
{
int u = read(), v = read();
int sz = ve[u].size();
for(int x=sz-1; x>=0; x--)
{
ve[v].push_back(ve[u][x]);
}
ve[u].clear();
}
else
{
int x = read(), z = read();
while(x)
{
if((*--ve[z].end()).first < x)
{
x -= (*--ve[z].end()).first;
ve[z].erase(--ve[z].end());
}
else
{
ans = (*--ve[z].end()).second;
(*--ve[z].end()).first -= x;
if((*--ve[z].end()).first == 0) ve[z].erase(--ve[z].end());
break;
}
}
printf("%d\n", ans);
}
}
return 0;
}
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 3;
int n, m, tot, h[maxn], t[maxn];
char op[7];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct line
{
int c, num, ch[2];
}p[maxn];
int main()
{
freopen("color.in", "r", stdin);
freopen("color.out", "w", stdout);
n = read(); m = read();
for(int i=1; i<=m; i++)
{
scanf("%s", op);
if(op[2] == 's')
{
int x = read(), y = read(), z = read();
p[++tot] = (line){y, x, h[z], 0};
if(h[z]) p[h[z]].ch[0] ? (p[h[z]].ch[1] = tot) : (p[h[z]].ch[0] = tot);
else t[z] = tot;
h[z] = tot;
}
else if(op[2] == 'p')
{
int x = read(), y = read();
while(p[h[y]].num < x)//猜对了，h等于0了，死循环了！！！
{
//printf("h[%d] = %d\n", y, h[y]);
//printf("x = %d\n", x);
if(!h[y]) exit(0);
x -= p[h[y]].num;//另一个新发现是x=4之后再也不减小了？？
int nxt = p[h[y]].ch[0] | p[h[y]].ch[1];
if(nxt)
{
//找到错因了：比较的是下一个，删的也是下一个，我怎么删成自己了？！
p[nxt].ch[0] == h[y] ? (p[nxt].ch[0] = 0) : (p[nxt].ch[1] = 0);
}
h[y] = nxt;//这个写在外面，似乎也不重要因为保证了不合法情况不存在
}
p[h[y]].num -= x;
printf("%d\n", p[h[y]].c);
}
else
{
int x = read(), y = read();
if(!h[x]) continue;
if(h[y])
{
p[h[y]].ch[0] ? (p[h[y]].ch[1] = h[x]) : (p[h[y]].ch[0] = h[x]);
p[h[x]].ch[0] ? (p[h[x]].ch[1] = h[y]) : (p[h[x]].ch[0] = h[y]);
}
else t[y] = h[x];
h[y] = t[x];//t[y] = h[x]我憨了，顺序没了
h[x] = t[x] = 0;
}
}
return 0;
}