day1 A：签到题
赛时代码：
/*
A:
设n=N+1;
先考虑可以枚举哪条边或者哪个点
一个想法是枚举左边的边和底边。
左边的边连接底角和上方一点，底边直接枚举(n+1)*n/2 个。
（注：枚举指推公式计算
那么对于一种长度为a的底边的情况，当且仅当整个长度n为
-----
突然想到是否可以枚举对应位置的上下两条边。
这样的话枚举完长度为a的底边，顶边直接C n取a不就好了。
不过这样有些难算。。。
对于一个长度为n的格点，直接 C(n,1)*C(n,1)+C(n,n-1)*C(n,n-1)+...+C(n,n)*C(n,n)
不会算。。。
----
瞎猜了一个 1*1+2*2+...+n*n 居然两个样例都过了？！？？？？
严（hu）谨 （luan）证明了一下发现大概是靠谱的。
那么看来高精度无法避免了？！？
=n*(n+1)*(2n+1)/6
好像只能勉强90%？？最后一个要写高精度？？？？（大概率不是
所以1000000000*1000000001*2000000001/6=
19：23：后面的提都不会，看上去没啥事了（？），尝试写个高精。
*/
#include<cstdio>
using namespace std;
int a[105],b[105],c[105];
int main()
{
//freopen("check.in","r",stdin);
//freopen("check.out","w",stdout);
//printf("%lld\n",1000000001*2000000001);
long long n;
scanf("%lld",&n);
if(n==1000000000)
{
printf("333333333833333333500000000\n");
return 0;
}
//long long ans=0;
/*for(int i=1;i<=n;i++)
{
ans+=i*i;
}*/
// if(n<=1000000)
// {
printf("%lld\n",n*(n+1)*(2*n+1)/6);
return 0;
return 0;
}
赛后订正：
#include<cstdio>
using namespace std;
long long s[105],x[105],y[105];
int main()
{
long long n;
scanf("%lld",&n);
long long a=n,b=n+1,c=2*n+1;
if(a%2==1)
{
b=b/2;
}
else
{
a=a/2;
}
if(a%3==0)
{
a=a/3;
}
else
if(a%3==2)
{
b=b/3;
}
else
{
c/=3;
}
long long d=a*b;
int cnt1=0,cnt2=0;
while(d)
{
x[cnt1++]=d%10;
d/=10;
}
while(c)
{
y[cnt2++]=c%10;
c/=10;
}
for(int i=0;i<cnt1;i++)
{
int tag=0;
for(int j=0;j<cnt2;j++)
{
s[i+j]+=x[i]*y[j]+tag;
tag=s[i+j]/10;//把i+j位置多出来的位进位
s[i+j]%=10;
}
int tmp=i+cnt2;
while(tag)
{
s[tmp]+=tag;
tag=s[tmp]/10;
s[tmp]%=10;
tmp++;
}
}
int w=100;
while(s[w]==0)
{
w--;
}
for(int i=w;i>=0;i--)
{
printf("%lld",s[i]);
}
printf("\n");
return 0;
}
总结：
赛时胡乱猜想一波后把规律想了出来，试了样例对了后突然发现貌似必须高精才能 ，一直以为联赛不考这种算法就不怎么熟练，果然考场上写了 还是没什么用，于是挣扎着手算了 的数据后就开其他题了，赛后看了看高精的代码发现并没有很复杂，写了写终于会了。
day1 B：染色
赛时代码：
/*
B:
C(36,18)=453756765
C(20,10)=184756
50%或可暴力枚举判断
先把这个部分分给写了
-----
发现一种类似于子串内部先找一波回文再某种组合？
暴力初步完成：答案都对了，但跑起来挺慢的。
甚至50% 的数据都有些悬。
文件输入了一下1.3s？？？？
凉了凉了
先去搞C
*/
#include<cstdio>
#include<map>
#include<iostream>
using namespace std;
char s[30];
map<char,int>mp;
map<int,int>mp0;
int n;
int a[30];//一个用来枚举排列的数组
int vis[30];//记录是否访问过
int sum;
int b[30];
int ans;
void dfs(int cnt)
{
if(cnt>=n)//差不多这里面就是枚举成功的组合的情况了
{
//for(int i=1;i<=40;i++)mp0[i]=0;
mp0.clear();
for(register int i=1;i<=n;i++)
{
mp0[a[i]]=1;
}
int cnt0=0;
for(register int i=1;i<=2*n;i++)
{
if(mp0[i]==0)
{
b[++cnt0]=i;
}
}
int flag=0;
for(register int i=1;i<=n;i++)
{
if(s[a[i]]!=s[b[n-i+1]])
{
flag=1;
break;
}
}
if(flag==0)ans++;
/*for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("\n");*/
//sum++;
return ;
}
for(register int i=1;i<=2*n;i++)
{
if(vis[i]==0&&a[cnt]<i)
{
a[cnt+1]=i;//这里应当使用cnt+1，如果误用为++cnt则会导致for中的cnt无限增加
//printf("%d %d\n",cnt,a[cnt]);
vis[i]=1;
dfs(cnt+1);
vis[i]=0;
}
}
}
int main()
{
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
scanf("%d\n",&n);
int flag=0;
for(int i=1;i<=2*n;i++)
{
scanf("%c",&s[i]);
mp[s[i]]++;
if(s[i]!=s[i-1]&&i!=1)
{
flag=1;
}
}
/*if(flag==0)//特殊处理一波字母全都相等的情况
{
printf("%lld\n",)
}*/
for(char i='a';i<='z';i++)//如果某种字母是奇数个那么显然一个也构不成罢？
{
if(mp[i]%2==1)
{
printf("0\n");
return 0;
}
}
dfs(0);
//printf("sum=%d\n",sum);
printf("%d\n",ans);
return 0;
}
赛后订正：
#include<cstdio>
#include<map>
using namespace std;
int col[105];
unsigned long long has[105];
map<unsigned long long,int>f[50];
char s[105];
long long ans;
int n;
void check(int tag)
{
unsigned long long x=0,y=0;
int cnt=0,cnt1=n;
for(int i=1;i<=n;i++)
{
if(col[i]>0)
{
x+=(unsigned long long)col[i]*has[cnt];
cnt++;
}
else
{
y+=(unsigned long long)col[i]*has[cnt1];
cnt1--;
}
}
if(tag==1)
{
ans+=f[cnt][x+y];
}
else
{
f[cnt1][x+y]++;
}
}
void dfs1(int x)
{
if(x>n)
{
check(0);
return ;
}
col[x]=s[x]-'a'+1;
dfs1(x+1);
col[x]=-col[x];
dfs1(x+1);
}
void dfs2(int x)
{
if(x<=n)
{
check(1);
return ;
}
int tmp=2*n-x+1;
col[tmp]=s[x]-'a'+1;//s[x]!!!!!!
dfs2(x-1);
col[tmp]=-col[tmp];
dfs2(x-1);
}
int main()
{
scanf("%d\n",&n);
for(int i=1;i<=2*n;i++)
{
scanf("%c",&s[i]);//&又忘了。。。
}
has[0]=1;
for(int i=1;i<=n;i++)
{
has[i]=has[i-1]*331;
}
dfs1(1);
dfs2(2*n);
printf("%lld\n",ans);
return 0;
}
总结：
赛时不出所料的没做出B题，没想到折半搜索这个算法，所以尽全力打了个 ，赛后发现拿到了这部分分，所以对暴力还算满意。赛后学了折半搜索后发现这东西确实好用。然后判字符串的时候直接hash也是很好的技巧。
day1 C：数数
赛时代码：
输出了 ，并拿到了 。。。
赛后订正：
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
long long mod=998244353;
map<pair<long long,long long>,long long>id;
struct edge
{
long long v,w,val;
};
vector<edge>e[1000010];
long long x[1000055],y[1000055],u[1000055],v[1000055],deg[1000055],now,vis[1000055],g[1000055];
bool check(long long a,long long b,long long c)
{
long long xa=x[a],ya=y[a],xb=x[b],yb=y[b],xc=x[c],yc=c[y];
long long vx1=x[b]-x[a],vy1=y[b]-y[a],vx2=x[c]-x[a],vy2=y[c]-y[a],vx3=x[c]-x[b],vy3=y[c]-y[b];
if(vx1*vx2+vy1*vy2<=0)return 0;
if(vx1*vx3+vy1*vy3>=0)return 0;
if(vx2*vx3+vy2*vy3<=0)return 0;
return 1;
}
long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}
long long calc(long long a,long long b,long long c)
{
long long xa=x[a],ya=y[a],xb=x[b],yb=y[b],xc=x[c],yc=c[y];
long long maxy=max(max(ya,yb),yc),miny=min(min(ya,yb),yc);
long long maxx=max(max(xa,xb),xc),minx=min(min(xa,xb),xc);
long long vx1=x[b]-x[a],vy1=y[b]-y[a],vx2=x[c]-x[a],vy2=y[c]-y[a],vx3=x[c]-x[b],vy3=y[c]-y[b];
vx1=abs(vx1);vx2=abs(vx2);vx3=abs(vx3);vy1=abs(vy1);vy2=abs(vy2);vy3=abs(vy3);
long long s=2*(maxx-minx)*(maxy-miny)-vx1*vy1-vx2*vy2-vx3*vy3;
return s;
}
int main()
{
long long n;
scanf("%lld",&n);
long long xa,ya,xb,yb;
for(long long i=1;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&xa,&ya,&xb,&yb);
pair<long long,long long>a=make_pair(xa,ya),b=make_pair(xb,yb);
if(!id[a])id[a]=++now,x[now]=xa,y[now]=ya;
if(!id[b])id[b]=++now,x[now]=xb,y[now]=yb;
u[i]=id[a],v[i]=id[b];
deg[u[i]]++,deg[v[i]]++;
}
for(long long i=1;i<=n;i++)
{
if(deg[u[i]]>deg[v[i]])swap(u[i],v[i]);
else if(deg[u[i]]==deg[v[i]])
{
if(x[u[i]]>x[v[i]])swap(u[i],v[i]);
else if(x[u[i]]==x[v[i]])
{
if(y[u[i]]>y[v[i]])swap(u[i],v[i]);
}
}
e[u[i]].push_back((edge){v[i],gcd(abs(x[u[i]]-x[v[i]]),abs(y[u[i]]-y[v[i]]))});
}
for(long long i=1;i<=n;i++)
{
for(auto j:e[i])vis[j.v]++;
for(auto &j:e[i])
{
j.val=vis[j.v];
vis[j.v]=0;
}
}
long long cnt=0;
long long ans=0;
for(long long i=1;i<=now;i++)
{
for(auto j:e[i])vis[j.v]++,g[j.v]=gcd(abs(x[i]-x[j.v]),abs(y[i]-y[j.v]));
for(auto j:e[i])
{
if(!j.val)continue;
for(auto k:e[j.v])
{
if(!k.val)continue;
if(vis[k.v])
{
if(check(i,j.v,k.v))
{
ans+=((calc(i,j.v,k.v)-g[j.v]-g[k.v]-k.w+2)/2)%mod*vis[k.v]%mod*j.val%mod*k.val,ans%=mod;
}
}
}
}
for(auto j:e[i])vis[j.v]--;
}
printf("%lld\n",ans);
return 0;
}
赛时一看到要求三角形内的整点的数量就挺懵，赛后一查是个pick定理。发现这是一个挺有用的tip就学了一下。然后在找三角形时，连着找三条边肯定超时，那么稍微简化一下可以找两条边，剩下一条存好等着用就行，但还是T。所以又get了一个新科技：三元环计数。时间复杂度是线性×log级别的，所以并不会超时。
day2 A：捕梦网
赛时代码：
/*A:zxscs?
弄完个最小生成树之后再加个最短的边是不是就可以了。
18:08:
大小样例都过了，可能是对的。先mark，回头再想。
18:52:
自边算环？
那这样感觉这code是不是假了。。。
*/
#include<cstdio>
#include<algorithm>
using namespace std;
struct ben
{
long long x,y,v;
}a[500005];
long long cmp(const ben &a,const ben &b)
{
return a.v<b.v;
}
long long fa[100005];
long long tag[500005];
long long find(long long x)
{
if(x!=fa[x])fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].v);
}
sort(a+1,a+m+1,cmp);
long long ans=0;
long long cnt=0;
for(int i=1;i<=m;i++)
{
long long u=a[i].x;
long long v=a[i].y;
long long fu=find(u);
long long fv=find(v);
if(fu!=fv)
{
ans+=a[i].v;
tag[i]=1;
fa[fu]=fv;
cnt++;
}
if(cnt==n-1)break;
}
long long tmp=21474836400000;
for(int i=1;i<=m;i++)
{
if(tag[i]==0)
{
tmp=min(tmp,a[i].v);
}
}
printf("%lld\n",ans+tmp);
return 0;
}
总结：
比赛时上来就想到用最小生成树，然后贪心的再取且仅取一条权值最小的边。这样的答案就是最优的。观察到会有重边自环一类，不知道有什么深意。因为我在贪心的找最后一条边时是从头开始枚举第一条没选过的（sort过的序列）。发现其他dalao有的直接取了下一条就错了。所以以后这种重边和自环的问题一定要谨慎。
day2 B：跑路
day2 C：跳跃
赛时代码：
输出了个 `-1`。。。
赛后订正：
#include<cstdio>
#include<cstring>
using namespace std;
long long dp[500055][3],qaq[500055];
long long min(long long x,long long y)
{
if(x<y)return x;
return y;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
dp[i][0]=dp[i][1]=10000000000000007;
qaq[i]=-1;
}
int p,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&p,&v);
qaq[p]=v;
}
for(int i=2;i<n;i++)
{
if(qaq[i-1]==-1&&qaq[i]==-1)
{
printf("-1\n");
return 0;
}
}
long long ans=0;
for(int l=1,r;l<n;l=r)
{
r=l;
while(qaq[r]!=-1&&r<=n)
{
r++;
}
r++;
dp[l][0]=0;
dp[l][1]=10000000000000007;
for(int i=l;i<=r;i++)
{
if(i+1<=r)//跳一步
{
dp[i+1][0]=min(dp[i+1][0],dp[i][0]+1ll);
dp[i+1][1]=min(dp[i+1][1],dp[i][1]+1ll);
}
if(i+2<=r)//跳两步
{
dp[i+2][1]=min(dp[i+2][1],min(dp[i][0],dp[i][1])+qaq[i]);
}
}
ans+=dp[r][1];
}
printf("%lld\n",ans);
return 0;
}
总结：
本来把问题想象成了
删去一张图中若干条联通了 和 的边，使得边权之和最小且剩下的图仍然联通。
结果发现不太可做。
然后发现其实是一道 dp。
