|
------------------------------7题弟弟，被各位半小时13题的大佬打惨了（滑稽）------------------------------------------- 签到题就不写了。 ? F ：Moving On??????????? (1247ms） 题意：给定大小为N的带点权，带边权的完全图，N<200。 然后Q次询问，每次给出(u,v,w)，让你求在除了起点终点的其他途经点的点权都<=w的条件下的最短路。 思路：可以离线做的话，显然就是需要排序了。 然后想到floyd就是一个用点更新的最短路算法。 那么我们把floyd的第一层按点权排个序即可。 那么第k层的dis[i][j]，就表示途经点都<=w[k]的最短路。 为了方便，这里所有的点权和询问的w都离散化了。 （比赛因为没有初始化WA了半天，哭）（网上看了其他人的写法大都是三维的，显然没必要，很明显是滚动的，在可以离线的情况下，第一维没什么用）。  #include<bits/stdc .h>
#define pii pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i )
using namespace std;
const int maxn=210;
const int maxm=20010;
int mp[maxn][maxn],b[maxn],tot,ans[maxm];
struct in{
int u,v,w,id;
};
vector<in>G[maxn];
pii a[maxn];
int main()
{
int T,N,M,C=0;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M);
rep(i,1,N) scanf("%d",&a[i].first),a[i].second=i;
rep(i,1,N) b[i]=a[i].first;
sort(b 1,b N 1);
tot=unique(b 1,b N 1)-(b 1);
rep(i,0,tot) G[i].clear();
rep(i,1,N) a[i].first=lower_bound(b 1,b tot 1,a[i].first)-b;
sort(a 1,a N 1);
rep(i,1,N) rep(j,1,N) scanf("%d",&mp[i][j]);
rep(i,1,M) {
in t;
scanf("%d%d%d",&t.u,&t.v,&t.w);
ans[i]=mp[t.u][t.v];
t.w=upper_bound(b 1,b tot 1,t.w)-b;
t.w--; t.id=i;
G[t.w].push_back(t);
}
rep(k,1,N) {
int tk=k; while(tk 1<=N&&a[tk 1].first==a[k].first) tk ;
rep(p,k,tk) {
rep(i,1,N)
rep(j,1,N){
int kk=a[p].second;
mp[i][j]=min(mp[i][j],mp[i][kk] mp[kk][j]);
}
}
for(int i=0;i<G[a[k].first].size();i ){
in t=G[a[k].first][i];
ans[t.id]=min(ans[t.id],mp[t.u][t.v]);
}
k=tk;
}
printf("Case #%d:\n", C);
rep(i,1,M) printf("%d\n",ans[i]);
}
return 0;
}View Code? G：Factories （1036ms） 题意：给定一个大小为N的无根树，让你选K个叶子，使得两两间距离和最短。 (N<1e5, K<100)； 思路：这类题可能会想到换根DP，然后这里想了想没必要 。??? 如果有度数大于1的，它就可以作为根，然后就是一个树上背包题，而谁作为根，效果是一样的，所以没必要换根DP。 ?? 然后发现想不出O(NK)的写法，所以瞎交了一发O(NK^2)。 居然过了。 玄学。 （知道NK写法的哥哥快告诉我啊） #include<bits/stdc .h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i )
using namespace std;
const int maxn=100010;
const ll inf=1LL<<60;
int Laxt[maxn],Next[maxn<<1],To[maxn<<1],len[maxn<<1],cnt;
int ind[maxn],rt,sz[maxn],K;
void add(int u,int v,int w){
Next[ cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; len[cnt]=w;
}
ll dp[maxn][101],ans;
void read(int &x){
x=0; char c=getchar();
while(c>'9'||c<'0') c=getchar();
while(c>='0'&&c<='9') x=x*10 c-'0',c=getchar();
}
void dfs(int u,int f)
{
sz[u]=0; int leaf=1; dp[u][0]=0;
for(int i=Laxt[u];i;i=Next[i]){
int v=To[i]; if(v==f) continue;
leaf=0; dfs(v,u);
for(int k=sz[u];k>=0;k--){
for(int j=min(K-k,sz[v]);j>=1;j--){
dp[u][k j]=min(dp[u][k j],dp[u][k] dp[v][j] 1LL*(K-j)*j*len[i]);
}
}
sz[u] =sz[v];
}
if(leaf) sz[u]=1,dp[u][1]=0;
if(sz[u]>=K) ans=min(ans,dp[u][K]);
}
int main()
{
int T,N,C=0,u,v,w;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&K);
rep(i,1,N) Laxt[i]=0; cnt=0;
rep(i,0,N 1) rep(j,0,K) dp[i][j]=inf; ans=inf;
rep(i,1,N) ind[i]=0;
rep(i,1,N-1){
read(u); read(v); read(w);
add(u,v,w); add(v,u,w);
ind[u] ; ind[v] ;
}
if(N==1||K<=1) ans=0;
else if(N==2) ans=len[1];
else {
rep(i,1,N) if(ind[i]>1) {
rt=i; break;
}
dfs(rt,0);
}
printf("Case #%d: %lld\n", C,ans);
}
return 0;
}View Code? K：Vertex Covers （1060ms） 题意：给定N点M边的无向图，每个点有点权。? 点覆盖表示某个点集S{}覆盖了所有的边，其贡献是点权S之积。 现在让你求所有的贡献之和。N<36，保证无重边，自环。 思路：点覆盖的问题，而且N比较小，不难想到状压。? 可以这里N最大为36，显然还需要一个折半枚举，然后想办法合并两边。 那么我们把点分为L，R两个集合。?? 那么边有三类： 1，两端点在L中； 2，两端点在R中； 3，两端点在L和R中各一个。 那么显然，对于1类边，两个端点至少一个要选；? 对于2类边同理；? 对于第3类边， 如果L中没选，那么R中必选，即补集的超集，而超集我们可以用高维前缀和搞定。? 所以这题就完了。 （那些100ms跑出来的人都是神仙吧） #include<bits/stdc .h>
#define rep(i,a,b) for(int i=a;i<=b;i )
using namespace std;
const int maxn=2000010;
int a[maxn],sum[maxn],ltl[40],ltr[40],rtr[40],Mod;
void MOD(int &x){ if(x>=Mod) x-=Mod;}
int main()
{
int T,N,M,u,v,C=0;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&N,&M,&Mod);
rep(i,0,N-1) scanf("%d",&a[i]);
rep(i,0,N-1) ltl[i]=ltr[i]=rtr[i]=0;
int L=(N 1)/2, R=N-L, ans=0;
rep(i,1,M){
scanf("%d%d",&u,&v);
u--, v--;
if(u>v) swap(u,v);
if(u<L){
if(v<L) ltl[u]|=(1<<v);
else ltr[u]|=(1<<(v-L));
}
else rtr[u]|=(1<<(v-L));
}
rep(i,0,(1<<R)-1){
int res=1;
rep(j,0,R-1){
if(i&(1<<j)) res=1LL*res*a[j L]%Mod;
else {
res=res*((rtr[j L]|i)==i);
if(!res) break;
}
}
sum[i]=res;
}
rep(i,0,R-1) {
rep(j,0,(1<<R)-1) {
if(!(j&(1<<i))) MOD(sum[j] =sum[j|(1<<i)]);
}
}
rep(i,0,(1<<L)-1){
int res=1,need=0;
rep(j,0,L-1) {
if(i&(1<<j)) res=1LL*res*a[j]%Mod;
else {
res=res*((ltl[j]|i)==i),need|=ltr[j];
if(!res) break;
}
}
MOD(ans =1LL*res*sum[need]%Mod);
}
printf("Case #%d: %d\n", C,ans);
}
return 0;
}View Code? 来源：https://www./content-4-431251.html |
|
|
