写给自己：主要要看的是B.F.E.G
总结：
1.对TSP问题认识不足。
2.B题模3这个条件的性质不清楚。
3.复数快速幂？不敢往复数想。
注意：为了阅读效果，我把头文件、快读快写删了。需完整代码可以看我提交
A.回文括号序列计数
ll solve(){
if(n==0)return 1;
return 0;
}C.末三位
直接快速幂
while(~scanf("%d",&n))
printf("%03d\n",ksm(5,n)%1000);D.划数
因为cnt>=11,所以其实是cnt这个数没动过，其他数操作到剩下一个数。特判下n=2。
while(cin>>n>>cnt){
rep(i,1,n)read(num[i]);
if(n==2){
if(num[1]==cnt){
cout<<num[2]<<endl;;
}
else{
cout<<num[1]<<endl;
}
}
else{
int res=0;
int flag=0;
rep(i,1,n){
if(!flag&&num[i]==cnt){
flag=1;
continue;
}
res=(res+num[i])%11;
}
cout<<res<<endl;
}
}I.贪吃蛇
显而易见就是求起点到终点的最短距离。给的图相当于路径权值都为1，直接BFS就行了。
const int maxn=1e2+10;
char mp[maxn][maxn];
int n,m;
int sx,sy,ex,ey;
struct node{
int x,y,step;
};
bool vis[maxn][maxn];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int solve(){
queue<node>que;
que.push({sx,sy,0});
vis[sx][sy]=1;
int res=inf;
while(!que.empty()){
node a=que.front();que.pop();
for(int i=0;i<4;++i){
int dx=a.x+dir[i][0];
int dy=a.y+dir[i][1];
if(dx<=0||dy<=0||dx>n||dy>m||vis[dx][dy]||mp[dx][dy]=='#')continue;
vis[dx][dy]=1;
if(dx==ex&&dy==ey)return (a.step+1)*100;
que.push({dx,dy,a.step+1});
}
}
return -1;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//clock_t c1 = clock();
//===========================================================
read(n),read(m);
read(sx),read(sy),read(ex),read(ey);
rep(i,1,n)scanf("%s",mp[i]+1);
cout<<solve()<<endl;
//===========================================================
//std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}
J.天空之城
显而易见这题就是判联通+MST，和起点没啥关系？记得开longlong
#define int ll
int n,q;
const int maxn=5e3+100;
int tot;
string tmp;
map<string,int>re;
struct node{
int u,v,val;
};
vector<node>da;
int s[maxn];
int find(int x){
return s[x]==x?x:s[x]=find(s[x]);
}
void merge(int x,int y){
x=find(x);
y=find(y);
if(x==y)return;
s[x]=y;
}
void solve(){
re.clear();
tot=0;
da.clear();
cin>>tmp;
rep(i,1,n)s[i]=i;
for(int i=0;i<q;++i){
string a,b;
int c;
cin>>a>>b>>c;
if(!re[a])re[a]=++tot;
if(!re[b])re[b]=++tot;
da.push_back({re[a],re[b],c});
}
sort(da.begin(),da.end(),[](const node&a,const node&b){
return a.val<b.val;
});
int res=0;
for(auto x:da){
int u,v,w;
u=x.u,v=x.v,w=x.val;
if(find(u)==find(v)){
continue;
}
res+=x.val;
merge(u,v);
}
int fa=find(1);
rep(i,2,n)if(fa!=find(i)){
cout<<"No!"<<endl;
return;
}
cout<<res<<endl;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//clock_t c1 = clock();
//===========================================================
IOS;
while(cin>>n>>q){
solve();
}
//===========================================================
//std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}F.组合数问题
我们联想下我们高中课堂上学二项式定理的时候是怎么证明奇数项和=偶数项和的：
不就是展开得到的吗？
这里利用的其实是-1的奇数次为-1，偶数次为1。
回到我们这里，我们现在要求4的倍数的，那么，显然，我们需要一个4次方是1和2次方符号相反的东西，学过fft的小伙伴肯定不陌生，这里我们想到了单位根,我们这里需要4次单位根，n=4带入：
。
来到这里，思路可能还不是很清晰，但是，我们带进去看看：
两式子相加其实可以发现：
成功地把2次倍数中4的倍数项和非4的倍数项分开，接下来，我们只要求的这一部分就行了，这不就是
?
结论：
之后我们写个复数类+快速幂就行了。Alan牛逼Orz
ll n;
struct Complex{
long long x,y;
Complex(long long xx=0,long long yy=0){
x=xx;
y=yy;
}
friend Complex operator+(const Complex&a,const Complex&b){return Complex((a.x+b.x)%mod,(a.y+b.y)%mod);}
friend Complex operator-(const Complex&a,const Complex&b){return Complex(((a.x-b.x)%mod+mod)%mod,((a.y-b.y)%mod+mod)%mod);}
friend Complex operator*(const Complex&a,const Complex&b){return Complex(((a.x*b.x-a.y*b.y)%mod+mod)%mod,((a.x*b.y+b.x*a.y)%mod+mod)%mod);}
};
Complex ksm_Com(Complex a,ll n){
Complex res={1,0};
while(n){
if(n&1)res=res*a;
a=a*a;
n>>=1;
}
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//clock_t c1 = clock();
//===========================================================
read(n);
ll res=ksm(2,n);
Complex res2=ksm_Com(Complex(1,1),n);
Complex res3=ksm_Com(Complex(1,-1),n);
ll ans=(res+res2.x+res3.x)%mod;
ans=(ans*ksm(4,mod-2))%mod;
cout<<ans<<endl;
//===========================================================
//std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}B.系数
这题没想到如此显而易见
Alan牛逼Orz。
好，然后，预处理阶乘（其实没准不处理都跑得过），然后跑卢卡斯就行了。
ll fac[5];
#define MOD(x) (((x)%mod+mod)%mod)
ll n,k;
void init(){
fac[0]=1;
for(ll i=1;i<5;++i)fac[i]=fac[i-1]*i%mod;
}
ll C(ll n,ll m){
return fac[n]*ksm(fac[n-m],mod-2)%mod*ksm(fac[m],mod-2)%mod;
}
ll Lucas(ll n,ll m){
if(!m) return 1;
return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//clock_t c1 = clock();
//===========================================================
int t;read(t);
init();
while(t--){
read(n),read(k);
write(MOD(Lucas(2*n,k)*(((2*n-k)&1)?-1:1)));putchar('\n');
}
//===========================================================
//std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}E.网格
这题没想出来是主要是没有想到行和列是互不影响的。由于行和列的贡献是互不干扰的，既：就算是一个鸽子，行选择了向右，列上也能选择上下列。因此，我们其实可以考虑分开来处理。如果单独看每一行的话，发现单独每一行又不干扰其他行，因此，我们考虑求每一行的贡献，然后，再考虑每一列的贡献。最后累加贡献即可。对于贡献的计算，其实就是每个格子要么选择向左，要不向右（对于列：向上或向下）两种决策，因此可以DP求最大贡献。
const int maxn=1e3+10;
int n,m;
int a[maxn][maxn];
int dp[maxn][3];
int cal(int x){
int res=x;
while(x){
res+=(x&1);
x>>=1;
}
return res;
}
int solve1(int idx,int pos,int predir){
if(pos>m)return 0;
int res=0;
if(~dp[pos][predir])return dp[pos][predir];
res=max(res,solve1(idx,pos+1,0)+(predir==1?cal((a[idx][pos-1]^a[idx][pos])):0));
res=max(res,solve1(idx,pos+1,1));
return dp[pos][predir]=res;
}
int solve2(int idx,int pos,int predir){
if(pos>n)return 0;
int res=0;
if(~dp[pos][predir])return dp[pos][predir];
res=max(res,solve2(idx,pos+1,0)+(predir==1?cal((a[pos-1][idx]^a[pos][idx])):0));
res=max(res,solve2(idx,pos+1,1));
return dp[pos][predir]=res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//clock_t c1 = clock();
//===========================================================
read(n),read(m);
rep(i,1,n){
rep(j,1,m){
read(a[i][j]);
}
}
int ans=0;
rep(i,1,n){
memset(dp,-1,sizeof(dp));
ans+=max(solve1(i,2,0),solve1(i,2,1));
//cerr<<max(solve1(i,2,0),solve1(i,2,1))<<endl;
}
rep(i,1,m){
memset(dp,-1,sizeof(dp));
ans+=max(solve2(i,2,0),solve2(i,2,1));
//cerr<<max(solve2(i,2,0),solve2(i,2,1))<<endl;
}
cout<<ans<<endl;
//===========================================================
//std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}G.机器人
这题有两种解法：DP或者贪心。
对于DP做法，这里我们可以把n个机器人理解为n个地点，然后，我们要安排访问顺序，求的一个极值，这其实就是一个旅行商问题。因此，考虑状压DP。
比赛的时候，一开始没敢写，因为对旅行商问题其实不是很熟悉，以为直接对于某个状态dp[i]有多种路径，会造成状态重叠（其实是我自己傻了，dp[i]应该为状态i的最大值，也就是最优子结构性质）。
复杂度：
对于贪心解法：其实是因为这道题的式子
我们假设对于i,j最优的顺序是i<j： 两边同时约掉了x，也就是说：
据此排序即可。类似于贪心经典问题：
国王的游戏
DP解法
#define int ll
struct node{
int a,b;
}da[25];
const int maxn=20;
ll dp[maxn+10][(1<<20)+10];
int n,x;
int solve(int pos,int con){
if(pos>n)return x;
if(~dp[pos][con])return dp[pos][con];
int res=0;
rep(i,1,n){
if((con>>(i-1)&1)==0){
res=max(res,da[i].a*solve(pos+1,con|(1<<(i-1)))+da[i].b);
}
}
return dp[pos][con]=res;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//clock_t c1 = clock();
//===========================================================
read(n),read(x);
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;++i){
int a,b;
read(a),read(b);
da[i]={a,b};
}
write(solve(1,0));
//===========================================================
//std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}贪心解法
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void read(T&x){
x=0;
char ch=getchar();
int f=1;
while(!isdigit(ch)){
if(ch=='-')f*=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+(ch-'0');
ch=getchar();
}x*=f;
}
template<typename T>
void write(T x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
//===============================================================
typedef __int128 ll;
struct node{
int a,b;
};
vector<node>da;
ll n,x;
int main(){
read(n),read(x);
for(int i=0;i<n;++i){
int a,b;
read(a),read(b);
da.push_back({a,b});
}
sort(da.begin(),da.end(),[](const node&a,const node&b){
return a.b*b.a+b.b>a.a*b.b+a.b;
});
ll res=x;
for(auto a:da){
res=res*a.a+a.b;
}
write(res);
return 0;
}
京公网安备 11010502036488号