Link:
C:
暴力$dfs$就好了
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,res=0; int dgt[15],cnt; void dfs(int dep,ll sum) { if(dep==cnt){res+=sum;return;} for(int i=dep+1;i<=cnt;i++) { ll t=0; for(int j=dep+1;j<=i;j++) t=t*10+dgt[j]; dfs(i,sum+t); } } int main() { scanf("%lld",&n); for(;n;n/=10) dgt[++cnt]=n%10; reverse(dgt+1,dgt+cnt+1);dfs(0,0); printf("%lld",res); return 0; }
D:
没有办法直接上暴力，但可以采取计算贡献的方式：
每个有色点都对周围的9个正方形恰好有1点贡献
将$9*k$个正方形用其左上角的坐标表示，排序后将相同的合并就是该正方形的个数了
最后用总的减去个数为$[1,9]$的就是个数为0的个数了
#include <bits/stdc++.h> using namespace std; #define X first #define Y second typedef long long ll; typedef pair<int,int> P; const int MAXN=1e5+10; P sqr[MAXN*10]; ll sum=0,cnt[15]; int n,m,k,x,y,tot; int dx[]={-2,-2,-2,-1,-1,-1,0,0,0}; int dy[]={-2,-1,0,-2,-1,0,-2,-1,0}; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=k;i++) { scanf("%d%d",&x,&y); for(int j=0;j<9;j++) { int fx=x+dx[j],fy=y+dy[j]; if(fx>0&&fy>0&&fx<=n-2&&fy<=m-2) sqr[++tot]=P(fx,fy); } } sort(sqr+1,sqr+tot+1); int cur=1; for(int i=2;i<=tot;i++) if(sqr[i]==sqr[i-1]) cur++; else cnt[cur]++,cur=1; if(k) cnt[cur]++;//不要忘记对末尾的处理 for(int i=1;i<=9;i++) sum+=cnt[i]; cnt[0]=1ll*(m-2)*(n-2)-sum; for(int i=0;i<10;i++) printf("%lld ",cnt[i]); return 0; }
E:
先来说说正解：拆点最短路
在每个站点中，对于每一个其能转换到的公司都新设立一个站点，并建立一个总站
也就是说，对于边$(u,v,c)$，建边$(u,u[c],1),(v,v[c],1),(u[c],v[c],0)$
这样体现了是否转换公司的抉择，直接在新图上求最短路就好了
但注意最后答案要除以2，毕竟这样建图每转换一次其实计算了2次1
我的做法又是极为感性的
在每个点都用一个$set$维护当前能达到最短距离时的末尾公司名，转移时贪心
感觉没什么问题，但不知道为什么在距离相同时一定要先处理编号较大的节点？请各位神犇们指点啊……
#include <bits/stdc++.h> using namespace std; #define X first #define Y second typedef pair<int,int> P; const int MAXN=1e5+10,INF=1<<27; int n,m,x,y,z,dist[MAXN]; set<int> s[MAXN]; vector<P> G[MAXN]; //必须要用set，因为可能dist最小时有多种公司供选择 struct cmp {//一定要编号大的先处理（原因未知） bool operator() (const P& a,const P& b) {return a.X!=b.X?a.X>b.X:a.Y<b.Y;} }; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); G[x].push_back(P(y,z));G[y].push_back(P(x,z)); } priority_queue<P,vector<P>,cmp > q; for(int i=2;i<MAXN;i++) dist[i]=INF; dist[1]=0;q.push(P(0,1)); while(!q.empty()) { P t=q.top();q.pop(); int u=t.Y,cost=t.X,tmp; if(cost>dist[u]) continue; for(int i=0;i<G[u].size();i++) { int v=G[u][i].X,col=G[u][i].Y; tmp=dist[u]+(!s[u].count(col)); if(tmp==dist[v]) s[v].insert(col); else if(tmp<dist[v]) { s[v].clear();s[v].insert(col); dist[v]=tmp,q.push(P(dist[v],v)); } } } printf("%d",(dist[n]==INF)?-1:dist[n]); return 0; }
F:
设游戏结束前使用了$x$张$b$，$y$张$c$
可以发现最终一共使用了$n+x+y$张卡片，且由于最后一张一定是$a$可以不用考虑
因此可以比较容易的写出一下的式子：
$res=sum_{p=0}^{m+k} C_{n−1+x+y}^{n-1}*3^{m+k−x−y}*sum_{0le xle m,0le yle k}[x+y=p]C_{p}^{x}$
为了将计算的时间降到$O(n)$，我们可以用递推的方式优化$sum C_{p}^{x}$
设$f(i)$表示$p=i$时该式的值，发现递推有三个阶段（假设$m<k$）：
1、$i<m$时$f(i)=sum_{j=0}^{i} C_i^j$
2、$mle i<k$时$f(i)=sum_{j=0}^{m} C_i^j$
3、$kle i$时$f(i)=sum_{j=i-k}^m C_i^j$
将这些式子放到杨辉三角形上可以发现：
1阶段时$f(i)=f(i-1)*2$（二项式系数和的基本结论）
2阶段时$f(i)=f(i-1)*2-C_{i-1}^m$（减掉右边界的值）
3阶段时$f(i)=f(i-1)*2-C_{i-1}^m-C_{i-1}^{i-1-k}$（减掉左右边界的值）
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=(3e5+10)*3,MOD=1e9+7; ll res=0,cur=1; int n,m,k,fac[MAXN],inv[MAXN]; ll quick_pow(ll a,ll b) { ll ret=1; for(;b;b>>=1,a=a*a%MOD) if(b&1) ret=ret*a%MOD; return ret; } int C(int a,int b) {if(a<b||b<0) return 0;return 1ll*fac[a]*inv[b]%MOD*inv[a-b]%MOD;} int main() { scanf("%d%d%d",&n,&m,&k); fac[0]=1; for(int i=1;i<MAXN;i++) fac[i]=1ll*fac[i-1]*i%MOD; inv[MAXN-1]=quick_pow(fac[MAXN-1],MOD-2); for(int i=MAXN-2;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%MOD; for(int i=n;i<=n+m+k;i++) (res+=C(i-1,n-1)*cur%MOD*quick_pow(3,n+m+k-i)%MOD)%=MOD, cur=(2*cur-C(i-n,m)+MOD-C(i-n,i-n-k)+MOD)%MOD; printf("%lld",res); return 0; }
优化方式涨姿势了