模拟赛四
得分
只有第三题得了 75 分……
T1
考场上写的超级暴力的暴力，然后 0 分。
正解
首先考虑最后形成的数组，从最小值看起，发现只有有奇数个的时候先手必胜，所以可以用异或统计出是否是先手必胜。
对于两个点之间的路径，直接暴力的统计他们之间的路径是会超时的，所以可以发现。
本图意为从（5,6）之间的路径，（1,2）之间的路径重复两次，所以正好抵消。
如图的两个路径，从根节点到分叉点的路径相同，也就是说，在异或时正好可以抵消掉，并不会影响结果。剩下的就是原本的路径。所以可以一开始预处理出根节点到所有点的路径权值异或和。
最后用所有方案数减去权值向同的点之间的方案数，即为答案。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline long long read() {
long long s = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
s = (s << 3) + (s << 1) + (ch ^ 48);
ch = getchar();
}
return s;
}
inline void write(long long x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int ds[500005];
int n,t;
struct nd{
int y,z;
};
vector<nd> v[500005];
void dfs(int x,int fa){
for(int i=0;i<v[x].size();i++){
if(v[x][i].y==fa) continue;
ds[v[x][i].y]=ds[x]^v[x][i].z;
dfs(v[x][i].y,x);
}
}
map<int,int> vis,tong,mp,ul;
int r;
signed main() {
srand(time(0));
int t;
mp[0]=1;
cin>>t;
for(int i=1;i<=500000;i++){
mp[i]=mp[i-1]*13331;
}
while(t--){
vis.clear();
tong.clear();
cin>>n;
for(int i=1;i<=n;i++) v[i].clear();
for(int i=1;i<=n;i++) ds[i]=0;
for(int i=1,x,y,z;i<n;i++){
cin>>x>>y>>z;
if(ul[z]==NULL) {
ul[z]=++r;
}
z=ul[z];
z=mp[z];
v[x].push_back({y,z});
v[y].push_back({x,z});
}
dfs(1,1);
int ans=(n-1)*n/2;
for(int i=1;i<=n;i++){
ans-=tong[ds[i]];
tong[ds[i]]++;
}
cout<<ans<<endl;
}
return 0;
}T2
虽然理解了题意，但是没有听懂……
T3
考场写的还行，能得到 75 分，全是ifelse。
做法
首先把 1 和 2，先结合。如果剩下得到是2，就让2自己结合，之后再把 2 与 3 结合或者用 4 去补充，否则就把 1 与自己结合，剩下的与 3 结合，或者用 4 去补充它。
代码
#include<bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
s = (s << 3) + (s << 1) + (ch ^ 48);
ch = getchar();
}
return s;
}
inline void write(long long x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int a[5],n;
int main() {
while(cin>>n){
int ans=0;
a[1]=a[2]=a[3]=a[4]=0;
for(int i=1;i<=n;i++) a[read()]++;
// if(a[1]+a[2]+a[2]+a[3]*3+a[4]*4==4||a[1]+a[2]+a[2]+a[3]*3+a[4]*4<3||a[1]+a[2]+a[2]+a[3]*3+a[4]*4==5) {
// cout<<-1<<"\n";
// continue;
// }
if(a[1]>a[2]){
ans+=a[2];
a[1]-=a[2];
a[3]+=a[2];
a[2]=0;
while(a[1]>=3) {
ans+=2;
a[1]-=3;
a[3]++;
}
if(a[1]>a[3]) a[1]-=a[3],ans+=a[3],a[4]+=a[3],a[3]=0;
else a[3]-=a[1],ans+=a[1],a[4]+=a[1],a[1]=0;
while(a[1]&&a[4]>=2) a[4]-=2,a[1]--,a[3]++,ans+=2;
if(a[1]) ans=-1;
}
else {
ans+=a[1],a[2]-=a[1],a[1]=0;
while(a[2]>=3) a[2]-=3,a[3]+=2,ans+=2;
while(a[4]&&a[2]) a[4]--,a[2]--,a[3]++,ans++;
if(a[2]==2) a[2]=0,a[4]++,ans+=2;
while(a[2]&&a[3]>=2){
a[3]-=2,a[4]+=2,a[2]--,ans+=2;
}
if(a[2]) ans=-1;
}
write(ans);
putchar('\n');
}
return 0;
}T4
考场本来写的是 O（qn） 复杂度的算法，但是不知到为什么，set里面总会少 6 这个数，所以直接 0 分。
我预想的做法
模拟修改的阶段，之后枚举三元组的中间值，用两个 set 维护所枚举到的当前的位置左右两边的值。
错误代码
（不知道有没有好心人帮我看看哪里写错了）
#include<bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
s = (s << 3) + (s << 1) + (ch ^ 48);
ch = getchar();
}
return s;
}
inline void write(long long x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int n,l,r,k,q,a[1000005];
int b[1000005];
int main() {
// freopen("circulate.in","r",stdin);
// freopen("circulate.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>q;
for(int i=1;i<=q;i++){
cin>>l>>r>>k;
for(int j=l;j<=r;j++){
if(j+k>r){
b[j+k-r-1+l]=a[j];
}
else {
b[j+k]=a[j];
}
}
for(int j=l;j<=r;j++) a[j]=b[j];
set<int> s,ss;
for(int j=1;j<=n;j++) s.insert(a[j]);
ss.insert(a[1]);
s.erase(a[1]);
int flag=0;
cout<<s.count(6);
for(int j=2;j<n;j++){
s.erase(a[j]);
if(*ss.begin()<a[j]&&*s.end()>a[j]){
flag=1;
break;
}
ss.insert(a[j]);
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}