- 留底击伤你的石头，从错误里吸收
先大致写几篇现场做出来的题吧还有几个后来两天补出来的题
我们现场写出来四道题，不过由于罚时高，我们队与牌子失之交臂了，呜呜呜真就差一点
B. Bitwise Exclusive-OR Sequence
现场的时候对于二进制下的三十位每一位都建图，也就是建30个图，然后染色，不过由于常数过大一直超时，不过好在最后使劲优化常数过了，下面是赛场时的代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll read(){
ll res=0;
char ch=getchar();
while(ch>='0'&&ch<='9'){
res+=(ch-'0');res*=10;ch=getchar();
}
return res/10;
}
int c[35][150000],flag,cnt1,cnt2;
int head[35][150000],nt[35][400005],val[35][400005],cea[35],to[35][400005];
ll pow2[40];
ll ans=0;
void add(int th,int u,int v,int w){
int& ce=cea[th];
to[th][++ce]=v,nt[th][ce]=head[th][u],head[th][u]=ce,val[th][ce]=w;
to[th][++ce]=u,nt[th][ce]=head[th][v],head[th][v]=ce,val[th][ce]=w;
}
void dfs(int th,int now,int color){
if(flag) return;
c[th][now]=color;
if(color==1)cnt1++;
else cnt2++;
for(int i=head[th][now];i;i=nt[th][i]){
int nxt=color,v=to[th][i];
if(val[th][i]==1) nxt=3-color;
if(c[th][v]==0)
dfs(th,v,nxt);
else
if(c[th][v]!=nxt){
flag=1;
return;
}
}
}
int main(){
pow2[0]=1;
for(int i=1;i<=30;i++) pow2[i]=pow2[i-1]*2;
int n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
ll w=read();
for(int j=0;j<=30;j++){
int tmp=pow2[j]&w;
if(tmp) tmp=1;
add(j,u,v,tmp);
//if(j==2) cout<<(pow2[j]&w)<<endl;
}
}
//cout<<endl;
for(int i=0;i<=30;i++){
for(int j=1;j<=n;j++){
if(c[i][j]) continue;
cnt1=0,cnt2=0;
dfs(i,j,1);
if(flag){
cout<<-1;
return 0;
}
/*if(i==2) cout<<cnt1<<
" "<<cnt2<<endl;*/
ans+=min(cnt1,cnt2)*pow2[i];
}
}
/*for(int i=head[2][3];i;i=nt[2][i])
cout<<to[2][i]<<" ";*/
printf("%lld",ans);
return 0;
}
后来赛后题解有提到过我的做法，提到了一种优化方式，就是30位完全可以一起染色，这是后来写的
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<int,int>>G[150000];
int n,m,col[150000],flag;
ll cnt0[40],cnt1[40];
ll ans;
void dfs(int now,int color){
if(flag) return;
col[now]=color;
for(int i=0;i<=30;i++){
if((color>>i)&1) cnt1[i]++;
else cnt0[i]++;
}
for(auto node:G[now]){
int v=node.first,w=node.second;
if(col[v]==-1) dfs(v,color^w);
else
if(col[v]!=(color^w)){
flag=1;
return;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) col[i]=-1;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
G[u].push_back(make_pair(v,w));
G[v].push_back(make_pair(u,w));
}
for(int i=1;i<=n;i++){
if(col[i]!=-1) continue;
memset(cnt1,0,sizeof(cnt1));
memset(cnt0,0,sizeof(cnt0));
dfs(i,0);
if(flag){
cout<<-1;
return 0;
}
for(int i=0;i<=30;i++){
ans+=min(cnt0[i],cnt1[i])*(1ll*(1<<i));
}
}
cout<<ans;
return 0;
}
E.Edward Gaming, the Champion
签到题不多说，edg牛逼！！！7777777
#include <bits/stdc++.h>
using namespace std;
char s[250000];
int ans;
int main(){
cin>>(s+1);
int len=strlen(s+1);
for(int i=1;i+4<=len;i++){
if(s[i]=='e'&&s[i+1]=='d'&&s[i+2]=='g'&&s[i+3]=='n'&&s[i+4]=='b') ans++;
}
cout<<ans;
return 0;
}
F.Encoded Strings I
就一模拟
#include <bits/stdc++.h>
using namespace std;
int n,cnt[2000],G[100];
char s[2000];
string ans="";
void getG(int len){
cnt[len+1]=0;
map<char,bool>m;
for(int i=len;i>=1;i--){
cnt[i]=cnt[i+1];
if(!m[s[i]]){
m[s[i]]=1;
cnt[i]++;
}
}
for(int i=1;i<=26;i++) G[i]=0;
for(int i=1;i<=26;i++){
for(int j=len;j>=1;j--){
if(s[j]=='a'+i-1){
G[i]=cnt[j+1];
break;
}
}
}
}
int main(){
cin>>n;
cin>>(s+1);
for(int len=1;len<=n;len++){
getG(len);
string tmp="";
for(int i=1;i<=len;i++){
int index=G[s[i]-'a'+1]+1;
char c='a'+index-1;
tmp+=c;
}
ans=max(ans,tmp);
}
cout<<ans;
return 0;
}
J.Luggage Lock
这也许是我赛场上最满意的一道题，出去上趟厕所想出来的
很多人都是用bfs写的而我用的是差分
因为这个很明显是一个区间加或者区间减的操作，所以枚举4位数达到目标数字的途径，不溢出，向上溢出（超过9），向下溢出（减到小于0）。然后计算把两个差分数组变成一样的需要几次
#include <bits/stdc++.h>
using namespace std;
char s1[10],s2[10];
int a[10],b[10],f[100][20],ki[20];
int aa[10],bb[10],ans,cnt;
void dfs(int now){
if(now>4){
cnt++;
for(int i=1;i<=4;i++) f[cnt][i]=ki[i];
return;
}
ki[now]=a[now];
dfs(now+1);
ki[now]=a[now]-10;
dfs(now+1);
ki[now]=a[now]+10;
dfs(now+1);
}
void solve(){
cnt=0;
cin>>(s1+1)>>(s2+1);
for(int i=1;i<=4;i++)
a[i]=s1[i]-'0',b[i]=s2[i]-'0';
dfs(1);
int ans=2147483647;
for(int l=1;l<=cnt;l++){
for(int i=1;i<=4;i++) aa[i]=f[l][i]-f[l][i-1];
for(int i=1;i<=4;i++) bb[i]=b[i]-b[i-1];
int cnt1=0,cnt2=0;
for(int i=1;i<=4;i++){
if(aa[i]>bb[i]) cnt1+=(aa[i]-bb[i]);
else cnt2+=(bb[i]-aa[i]);
}
ans=min(ans,min(cnt1,cnt2)+abs(cnt1-cnt2));
}
cout<<ans<<endl;
}
int main(){
int T;
cin>>T;
while(T--)
solve();
return 0;
} 然后接下来是我这两天补的三道题，后边可能还会断断续续的更新，不过那些题都很有难度，所以得多搞一阵子了
H.Line Graph Matching
当边数是偶数时，所有边都可以被匹配完。当边数是奇数时，恰好有一条边不会被匹配，如果是非割边，这条边可以不被匹配，如果是割边，且割去这条边之后两侧边数均为偶数，则这条边也可以不被匹配。当时不会用tarjan 2333333
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,dfn[150000],low[150000],tim,siz[150000];
ll sum;
vector<pair<int,int>>G[150000];
void tarjan(int now,int fa){
dfn[now]=low[now]=++tim;
for(auto node:G[now]){
int v=node.first,w=node.second;
if(v==fa) continue;
if(!dfn[v]){
siz[now]++;
tarjan(v,now);
siz[now]+=siz[v];
low[now]=min(low[now],low[v]);
}
else{
low[now]=min(low[now],dfn[v]);
if(dfn[v]>dfn[now]) siz[now]++;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
G[u].push_back(make_pair(v,w)),G[v].push_back(make_pair(u,w));
sum+=w;
}
if(m%2==0){
cout<<sum;return 0;
}
tarjan(1,0);
ll ans=0;
for(int i=1;i<=n;i++){
for(auto node:G[i]){
int v=node.first,w=node.second;
if(dfn[v]<dfn[i]) continue;
if(low[v]<=dfn[i]||siz[v]%2==0) ans=max(ans,sum-w);
}
}
cout<<ans;
return 0;
}
L.Perfect Matchings
思维难度不大，一个树上背包，再来一个容斥
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
vector<int>G[4005];
int siz[4005];
ll f[4005][2005][2],g[2005][2];
ll p[2005];
const int mod=998244353;
void dfs(int now,int fa){
f[now][0][0]=1;
siz[now]=1;
for(auto v:G[now]){
if(v==fa) continue;
dfs(v,now);
for(int i=0;i<=n+5;i++) g[i][0]=g[i][1]=0;
for(int i=0;i<=siz[now]/2;i++)
for(int j=0;j<=siz[v]/2;j++){
if(j){
g[i+j][0]+=(f[v][j][0]+f[v][j][1])%mod*f[now][i][0]%mod;
g[i+j][1]+=(f[v][j][0]+f[v][j][1])%mod*f[now][i][1]%mod;
}
g[i+j+1][1]+=f[now][i][0]*f[v][j][0]%mod;
}
siz[now]+=siz[v];
for(int i=0;i<=siz[now]/2+1;i++) f[now][i][0]+=g[i][0],f[now][i][1]+=g[i][1],
f[now][i][0]%=mod,f[now][i][1]%=mod;
}
}
int main(){
cin>>n;
for(int i=1;i<2*n;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v),G[v].push_back(u);
}
dfs(1,0);
p[0]=1;
for(int i=1;i<=n;i++) p[i]=(p[i-1]*(2*i-1))%mod;
ll ans=p[n];
//cout<<ans<<endl;
int tmp=-1;
for(int i=1;i<=n;i++){
ans+=tmp*(f[1][i][0]+f[1][i][1])*p[n-i];
//cout<<f[1][i][0]<<" "<<f[1][i][1]<<endl;
ans+=mod,ans%=mod;
tmp*=-1;
}
cout<<ans;
return 0;
}
M.String Problem
还是思维难度不大，不过当时现场没看到这道题
kmp，或者AC自动机就行
#include <bits/stdc++.h>
using namespace std;
char s[1000005];
int nxt[1000005];
int main(){
scanf("%s",s+1);
int len=strlen(s+1);
cout<<"1 1"<<endl;
int head=1,tot=1;
for(int i=2;i<=len;i++){
while(tot!=nxt[tot]&&s[head+nxt[tot]]<s[i]) head=head+(tot-nxt[tot]),tot=nxt[tot];
if(s[i]==s[head+nxt[tot]]&&tot){
tot++;
nxt[tot]=nxt[tot-1]+1;
}
else{
tot++;
nxt[tot]=0;
}
printf("%d %d\n",head,i);
}
return 0;
}
下面来做做总结，或许这一场打完后还是没有拿到牌子，不过很接近了，这让我感觉到了很大的希望，接下来猛猛淦！！！先说说这次所存在的问题，第一点就是一个团队配合的事情，大家互相讨论吧也没有一个很有效的信息交换，各抒己见之后，基本没有很大信息交换，然后团队也没有一个很明确的分工。其次就是透过本场比赛，发现本来自己并不在意的知识点出了好多题啊！！！
下一场努力吧！终须会时辰到，别怕
Comments | NOTHING