2018-team7-T04
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
* [wiki:Summer2018Team 返回上层]
* [wiki:2018-team7 队伍主页]
* [wiki:2018-team7-T03 上场比赛]
* [wiki:2018-team7-T05 下场比赛]
== 流水账 ==
比赛链接：https://vjudge.net/contest/261537
[[Image(submit04.png,500px)]]
[[Image(T04.png,800px)]]
先做的D 打了个表 '''D1Y34'''[[br]]
wsh/zzh nb! '''F1Y37'''[[br]]
yrb sb '''L1Y78'''[[br]]
wsh '''A2Y116'''[[br]]
yrb '''C3Y172'''[[br]]
wsh debuging..............[[br]]
yrb/zzh xjb gao M[[br]]
== 总结 ==
mid-last GG
=== IDrandom(yrb) ===
forget mod
=== CtrlCV(wsh) ===
too much memset
=== godspeedcurry(zzh) ===
read problems not bad but have to solve some problems by yourself you know
just give some ideas to my teammate
try to solve problem L finally but failed
== 题解 ==
A:wsh
B:
C:dp[i][S]=dp[i-1][S]+/-dp[i-1][S'](u,v in S)
D:regulation
E:
F:wsh
G:
H:
I:
J:
K:
L:simulation
M:
== 补题 ==
|| Contest Name || A || B || C || D || E || F || G || H || I || J || K || L || M ||
||2018 - Multi-University Training 3 || O || - || O || O || - || O || * || - || * || - || - || O || * ||
O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的 -:赛后待补 *:真-赛后待补
* [wiki:Summer2018Team 返回上层]
* [wiki:2018-team7 队伍主页]
* [wiki:2018-team7-T03 上场比赛]
* [wiki:2018-team7-T05 下场比赛]
'''F题'''
两个人最后的异或和=Xsum
Xsum==0的时候怎么玩都是平局
树是一个二分图
第一个人可以选其中一边来确保自己最大
比赛中zzh把结论猜出来了 证明by: wsh
{{{
#!c
#include <bits/stdc++.h>
using namespace std;
int w[102000];
int main(){
int T;
ios::sync_with_stdio(0);
cin>>T;
while(T--){
int n;
cin>>n;
int sum=0;
for(int i=1;i<=n;i++) cin>>w[i],sum^=w[i];
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
}
if(!sum) puts("D");
else puts("Q");
}
return 0;
}
}}}
'''D题'''
欧拉函数（合数）的第k个
打表。。
{{{
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int cal(int x){
int ans=0;
for(int i=1;i<=x;++i){
if(__gcd(i,x)==1){
ans++;
}
}
return ans;
}
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
if(x==1)printf("5\n");
else printf("%d\n",x+5 );
}
return 0;
}
}}}
'''L题'''
模拟 补了2h，学长还是强啊 = =
{{{
#include <bits/stdc++.h>
using namespace std;
#define ll long long
char G[1025][1025];
int s[]={2,1,0,0,0};
int e[]={4,4,4,3,2};
char block[10][10]={
"..+-+",
"././|",
"+-+.+",
"|.|/.",
"+-+.."
};
void putblock(int x,int y){
for(int i=0;i<=4;++i){
for(int j=s[i];j<=e[i];j++){
G[x+i][y+j]=block[i][j];
}
}
}
void init(){
memset(G,'.',sizeof G);
}
void print(int n,int m){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
printf("%c",G[i][j]);
}
printf("\n");
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
init();
int width=2*a+2*b+1;
int height=2*b+2*c+1;
for(int i=1;i<=b;i++){
for(int j=c;j>=1;j--){
for(int k=1;k<=a;k++){
putblock( (i-1)*2+j*2-1, (b-i)*2+1+(k-1)*2 );
}
}
}
print(height,width);
}
return 0;
}
}}}
A 单调队列
注意不要用stl 很慢
{{{
!#C
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 1e7+20;
typedef pair<ll,ll> Pair;
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define popb pop_back
ll a[MAXN];
Pair DQ[MAXN];
ll front,back;
int main(){
int T;
scanf("%d",&T);
while(T--){
ll n,m,k,p,q,r,MOD;
ll ans1=0;
ll ans2=0;
scanf("%lld %lld %lld %lld %lld %lld %lld",&n,&m,&k,&p,&q,&r,&MOD);
// printf("%lld\n",n );
for(int i=1;i<=k;++i){
scanf("%lld",&a[i]);
}
for(int i=k+1;i<=n;i++){
a[i]=(p*a[i-1]+q*i+r)%MOD;
}
DQ[back=1]=mp(a[1],1);
front=0;
for(int i=2;i<=m;++i){
while(back>front&&a[i]>DQ[back].first){
--back;
}
DQ[++back]=(mp(a[i],i));
}
for(ll i=1;i<=n-m+1;++i){
ans1+=(DQ[front+1].first^i);
if(DQ[front+1].second==i) ++front;//单调队列的第一个数是滑动区间的第一个数 把它丢掉
while(back>front&&a[i+m]>DQ[back].first){
--back;
}
DQ[++back]=(mp(a[i+m],i+m));
}
DQ[back=1]=mp(a[n],n);
front=0;
for(int i=n-1;i>=n-m+1;--i){
while(back>front&&a[i]>DQ[back].first){
--back;
}
DQ[++back]=(mp(a[i],i));
}
for(ll i=n-m+1;i>=1;--i){
ans2+=((back-front)^(i));
if(DQ[front+1].second==i+m-1) ++front;//单调队列的第一个数是滑动区间的第一个数 把它丢掉
while(back>front&&a[i-1]>=DQ[back].first){
--back;
}
DQ[++back]=(mp(a[i-1],i-1));
}
printf("%lld %lld\n",ans1,ans2);
}
return 0;
}
}}}流水账
比赛链接：https://vjudge.net/contest/261537
先做的D 打了个表 D1Y34[[br]]
wsh/zzh nb! F1Y37[[br]]
yrb sb L1Y78[[br]]
wsh A2Y116[[br]]
yrb C3Y172[[br]]
wsh debuging..............[[br]]
yrb/zzh xjb gao M[[br]]
总结
mid-last GG
IDrandom(yrb)
forget mod
CtrlCV(wsh)
too much memset
godspeedcurry(zzh)
read problems not bad but have to solve some problems by yourself you know
just give some ideas to my teammate
try to solve problem L finally but failed
题解
A:wsh
B:
C:dp[i][S]=dp[i-1][S]+/-dp[i-1][S'](u,v in S)
D:regulation
E:
F:wsh
G:
H:
I:
J:
K:
L:simulation
M:
补题
| Contest Name | A | B | C | D | E | F | G | H | I | J | K | L | M |
| 2018 - Multi-University Training 3 | O | - | O | O | - | O | * | - | * | - | - | O | * |
O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的 -:赛后待补 *:真-赛后待补
F题
两个人最后的异或和=Xsum
Xsum==0的时候怎么玩都是平局
树是一个二分图
第一个人可以选其中一边来确保自己最大
比赛中zzh把结论猜出来了 证明by: wsh
#include <bits/stdc++.h>
using namespace std;
int w[102000];
int main(){
int T;
ios::sync_with_stdio(0);
cin>>T;
while(T--){
int n;
cin>>n;
int sum=0;
for(int i=1;i<=n;i++) cin>>w[i],sum^=w[i];
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
}
if(!sum) puts("D");
else puts("Q");
}
return 0;
}
D题
欧拉函数（合数）的第k个
打表。。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int cal(int x){
int ans=0;
for(int i=1;i<=x;++i){
if(__gcd(i,x)==1){
ans++;
}
}
return ans;
}
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
if(x==1)printf("5\n");
else printf("%d\n",x+5 );
}
return 0;
}
L题
模拟 补了2h，学长还是强啊 = =
#include <bits/stdc++.h>
using namespace std;
#define ll long long
char G[1025][1025];
int s[]={2,1,0,0,0};
int e[]={4,4,4,3,2};
char block[10][10]={
"..+-+",
"././|",
"+-+.+",
"|.|/.",
"+-+.."
};
void putblock(int x,int y){
for(int i=0;i<=4;++i){
for(int j=s[i];j<=e[i];j++){
G[x+i][y+j]=block[i][j];
}
}
}
void init(){
memset(G,'.',sizeof G);
}
void print(int n,int m){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
printf("%c",G[i][j]);
}
printf("\n");
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
init();
int width=2*a+2*b+1;
int height=2*b+2*c+1;
for(int i=1;i<=b;i++){
for(int j=c;j>=1;j--){
for(int k=1;k<=a;k++){
putblock( (i-1)*2+j*2-1, (b-i)*2+1+(k-1)*2 );
}
}
}
print(height,width);
}
return 0;
}
A 单调队列
注意不要用stl 很慢
!#C
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 1e7+20;
typedef pair<ll,ll> Pair;
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define popb pop_back
ll a[MAXN];
Pair DQ[MAXN];
ll front,back;
int main(){
int T;
scanf("%d",&T);
while(T--){
ll n,m,k,p,q,r,MOD;
ll ans1=0;
ll ans2=0;
scanf("%lld %lld %lld %lld %lld %lld %lld",&n,&m,&k,&p,&q,&r,&MOD);
// printf("%lld\n",n );
for(int i=1;i<=k;++i){
scanf("%lld",&a[i]);
}
for(int i=k+1;i<=n;i++){
a[i]=(p*a[i-1]+q*i+r)%MOD;
}
DQ[back=1]=mp(a[1],1);
front=0;
for(int i=2;i<=m;++i){
while(back>front&&a[i]>DQ[back].first){
--back;
}
DQ[++back]=(mp(a[i],i));
}
for(ll i=1;i<=n-m+1;++i){
ans1+=(DQ[front+1].first^i);
if(DQ[front+1].second==i) ++front;//单调队列的第一个数是滑动区间的第一个数 把它丢掉
while(back>front&&a[i+m]>DQ[back].first){
--back;
}
DQ[++back]=(mp(a[i+m],i+m));
}
DQ[back=1]=mp(a[n],n);
front=0;
for(int i=n-1;i>=n-m+1;--i){
while(back>front&&a[i]>DQ[back].first){
--back;
}
DQ[++back]=(mp(a[i],i));
}
for(ll i=n-m+1;i>=1;--i){
ans2+=((back-front)^(i));
if(DQ[front+1].second==i+m-1) ++front;//单调队列的第一个数是滑动区间的第一个数 把它丢掉
while(back>front&&a[i-1]>=DQ[back].first){
--back;
}
DQ[++back]=(mp(a[i-1],i-1));
}
printf("%lld %lld\n",ans1,ans2);
}
return 0;
}