比赛结果

A Square Inequality

直接按照题目意思模拟即可。

B Intersection

枚举 $x$ ，因为范围只有 $1 \sim 1000$ ，可以暴力。

#include<bits/stdc++.h>
using namespace std;

#define maxn 105
typedef long long ll;
ll n,a[maxn],b[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++) cin>>b[i];
    ll counter=0;
    for(int i=1;i<=1000;i++){
        bool flag=false;
        for(int j=1;j<=n;j++)
            if(! (a[j]<=i && i<=b[j]))
                flag=true;
        if(!flag) counter++;
    }
    cout<<counter<<endl;
    return 0;
}

C IPFL

比以往难很多，考场上卡了好久最后才 A。
我们知道，变换两次之后字符串其实是不变的，也就是说，我们可以尝试先不考虑变换。
比如，我们先把一个长度为 $2n$ 的字符串的第 $x$ 个和第 $y$ 个字符交换；然后变换一次。
此时，第 $x$ 个字符去了第 $(x+n) \bmod 2n$ 处，第 $y$ 个字符同理！
也就是说，在这一次操作之前翻转了奇数次，这一次操作的 $x,y$ 要进行上述变换（注意，余数可能为 $0$ ，特判一下让它变成 $2n$ ）。
最后，如果一共反转了奇数次，还是需要变换一次。
这个难度和以往的 D 差不了多少。
考试的时候最开始想成了交换对后面的变换的影响导致错误，以后要细心一点（差点就没看出来，导致时间较晚）。看来现在的 C 不可小瞧。但还是要自信！

代码：

#include<bits/stdc++.h>
using namespace std;
string str;
int n,q,t,a,b;
int main(){
    cin>>n>>str>>q;
    bool sum=false;
    while(q--){
        cin>>t>>a>>b;
        if(t==1){
            if(sum){
                a+=n-1; a%=2*n; a++;
                b+=n-1; b%=2*n; b++;
            }
            char temp=str[a-1];
            str[a-1]=str[b-1];
            str[b-1]=temp;
        }else{
            sum=!sum;
        }
    }
    if(sum) cout<<str.substr(n,n)+str.substr(0,n);
    else cout<<str;
    return 0;
}

D RGB Coloring 2

ABC198 的 D 也是搜索考场没做出来……因为想复杂了

有了上次的经验，我决定自信地试一下暴力 dfs ：
定义函数 $\text{dfs}(x)$ 表示把 $x \sim n$ 这些点染色的方案数；
如果可以染成红色，那么标记，往 $\text{dfs}(x+1)$ 爆搜；其他两种颜色同理。

然后你发现 TLE 了。考虑优化：

如果 $x$ 点没有连边，直接返回 $3 \times \text{dfs}(x+1)$ ，因为这个点不受控。就过了。

代码：

#include<bits/stdc++.h>
using namespace std;
 
#define maxn 2010
#define int long long
 
struct Edge{
    int to,nxt;
}edge[maxn];
int head[maxn],tot;
 
void add(int u,int v){
    tot++;
    edge[tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
int n,m,u,v;
int col[maxn],counter;
bool isok(int x,int color){
    for(int i=head[x];i;i=edge[i].nxt){
        int tmp=edge[i].to;
        if(col[tmp]==color) return false;
        }
    return true;
}
int dfs(int x){
    if(x==n+1) return 1;
    int ord=0;
    for(int i=head[x];i;i=edge[i].nxt){
        ord++;
    }
    if(ord==0) return 3*dfs(x+1);
    int cnt=0;
    for(int i=1;i<=3;i++){
        if(isok(x,i)){
            col[x]=i;
            cnt+=dfs(x+1);
            col[x]=0;
        }
    }
    return cnt;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        add(u,v); add(v,u);
    }
    cout<<dfs(1);
    return 0;
}

E Permutation

赛场上没时间了没做出来，赛后做也没做对。反正是状压，有空补。

ABC199 比赛总结