比赛结果
A Square Inequality
直接按照题目意思模拟即可。
B Intersection
枚举 ，因为范围只有
，可以暴力。
#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。
我们知道，变换两次之后字符串其实是不变的，也就是说，我们可以尝试先不考虑变换。
比如，我们先把一个长度为 的字符串的第
个和第
个字符交换；然后变换一次。
此时，第 个字符去了第
处，第
个字符同理！
也就是说，在这一次操作之前翻转了奇数次，这一次操作的 要进行上述变换（注意，余数可能为
，特判一下让它变成
）。
最后，如果一共反转了奇数次，还是需要变换一次。
这个难度和以往的 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 ：
定义函数 表示把
这些点染色的方案数；
如果可以染成红色，那么标记，往 爆搜；其他两种颜色同理。
然后你发现 TLE 了。考虑优化：
如果 点没有连边，直接返回
，因为这个点不受控。就过了。
代码：
#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
赛场上没时间了没做出来，赛后做也没做对。反正是状压，有空补。
