j ∈ [ 1 , i )} 附本题代码 ——————————————————————
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) (((x)>0)?(x):-(x)) const int N = 3000+10; const int MOD = 1e9+7; int n,m,k; struct node { LL x,c; }a[N]; LL dp[N][2]; bool cmp(node A,node B){ return A.x<B.x; } LL sum[N]; int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].c); sort(a+1,a+n+1,cmp); sum[0]=0; for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].x; dp[1][1] = a[1].c; dp[2][1] = a[1].c+a[2].c; dp[2][0] = a[1].c+a[2].x-a[1].x; for(int i=3;i<=n;i++){ dp[i][1]=a[i].c+min(dp[i-1][1],dp[i-1][0]); dp[i][0]=dp[1][1]+(sum[i]-sum[1]-a[1].x*(i-1)); for(int j=2;j<i;j++){ dp[i][0]=min(dp[i][0],dp[j][1]+(sum[i]-sum[j]-a[j].x*(i-j))); } } // for(int i=1;i<=n;i++) printf("%lld ",sum[i]); puts(""); // for(int i=1;i<=n;i++) printf("%lld ",dp[i][1]); puts(""); // for(int i=1;i<=n;i++) printf("%lld ",dp[i][0]); puts(""); printf("%lld\n",min(dp[n][1],dp[n][0])); } return 0; }
C HDU 6025 Coprime Sequence ———————————————————————————————————————— 给你一个序列,任选一个元素去掉,使得剩下的元素gcd值最大,问你gcd的最大值是多少
因为要去掉一个,很容易想到预处理前缀gcd和后缀gcd,然后O(n)枚举去掉的元素即可,同事维护结果的最大值
附本题代码 ——————————————————————
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) (((x)>0)?(x):-(x)) const int N = 100000+10; const int MOD = 1e9+7; int n,m,k; int a[N],pre[N],suf[N]; int main(){ int _; scanf("%d",&_); while(_--){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } pre[1]=a[1],suf[n]=a[n]; for(int i=2;i<=n;i++){ pre[i]=__gcd(pre[i-1],a[i]); } for(int i=n-1;i;i--){ suf[i]=__gcd(suf[i+1],a[i]); } // for(int i=1;i<=n;i++) printf("%d ",pre[i]);puts(""); // for(int i=1;i<=n;i++) printf("%d ",suf[i]);puts(""); int mx = max(suf[2],pre[n-1]); for(int i=2;i<n;i++){ mx = max(mx,__gcd(suf[i+1],pre[i-1])); } printf("%d\n",mx); } return 0; }
D HDU 6026 Deleting Edges ———————————————————————————————————————— 打给就是给你一个完全图,然后问你满足每个点到0节点的距离都是原图上的最小距离的生成树的个数
不会、、
------------------------Update-----------------------------
首先处理出来 两点间最短路,用floyd即可
然后考虑枚举每一条边,如果这条边<u,v>在最短路上那么对于点v来说,生成树上有这条边就能保证距离最短
然后统计每个点的这样的边的个数,乘一起就好.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 # include <bits/stdc++.h> typedef long long int LL; using namespace std; const int N = 2e5+7; const int MOD = 1e9+7; /****************************************************/ int n; char a[55][55]; int b[55][55]; int dis[55][55]; LL ans[55]; int main(){ while(~scanf("%d",&n)){ memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++)scanf("%s",a[i]+1); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ b[i][j]=dis[i][j]=a[i][j]-'0'; if(b[i][j]==0) b[i][j]=dis[i][j]=1000000000; } b[i][i]=dis[i][i]=0; } // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++) // printf("%d ",dis[i][j]); // puts(""); // } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++) // printf("%d ",dis[i][j]); // puts(""); // } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&dis[1][i]+b[i][j]==dis[1][j]) ans[j]++; LL res = 1; for(int j=1;j<=n;j++) if(ans[j]>0) res=res*ans[j]%MOD; printf("%I64d\n",res); } return 0; }
E HDU 6027 Easy Summation ———————————————————————————————————————— 让你计算
∑ i = 1 n i k \sum_{i=1}^n i^k i = 1 ∑ n i k
因位数据范围较小,只要快速幂计算i k i^k i k 就好了,如果数据特别大的话 需要矩阵乘法做
附本题代码 ——————————————————————
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) (((x)>0)?(x):-(x)) const int N = 65535+10; const int MOD = 1e9+7; int n,m,k; LL qmod(LL a,LL b){ LL res = 1ll; while(b){ if(b&1) res=res*a%MOD; b>>=1,a=a*a%MOD; } return res; } int main(){ int _; while(~scanf("%d",&m)){ for(int i=1;i<=m;i++){ scanf("%d%d",&n,&k); LL ans = 0; for(int j=1;j<=n;j++){ ans+=qmod(j,k); if(ans>MOD) ans-=MOD; } printf("%lld\n",ans); } } return 0; }
#F HDU 6028 Forgiveness ————————————————————————————————————————
没读题,不会,没人出啊.
G HDU 6029 Graph Theory ———————————————————————————————————————— 按照规则有一个图,然你在这个图上找一个完美匹配 规则如下: 1 将这个点u和标号小于u的点连一个边, 2 没有操作.
其实很简单,我们只要顺序遍历下来,如果是1的时候,前面有一个节点没有匹配,那就和当前点匹配上,
最后所有节点都匹配上yes否则no
附本题代码 ——————————————————————
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) (((x)>0)?(x):-(x)) const int N = 3000+10; const int MOD = 1e9+7; int n,m,k; int main(){ int _; scanf("%d",&_); while(_--){ scanf("%d",&n); int flag = 0,x; int sum = 1; for(int i=2;i<=n;i++){ scanf("%d",&x); sum++; if(x==1&&sum>=2) sum-=2; } if(sum==0) puts("Yes"); else puts("No"); } return 0; }
H HDU 6030 Happy Necklace ———————————————————————————————————————— 现在有n这么长的手链,你有红色的,蓝色的石子,保证在连续奇数的区间内红色石子数不小于蓝色石子数,问方案数
首先对于保证在连续奇数的区间内红色石子数不小于蓝色石子数,
,很容易发现只要满足不存在 ‘蓝蓝’,‘蓝红蓝’,这两种子串就好了,
然后应该就能构造了,但是我这智商够早不出来啊,
于是贯彻遇事不决先打表
的宗旨,
x 2 3 4 5 6 … n ans(x) 3 4 6 9 13 … ans(i-1)+ans(i-3)
然后构造矩阵就好了
[ a n s ( i + 2 ) a n s ( i + 1 ) a n s ( i ) ] × [ 1 1 0 0 0 1 1 0 0 ] = [ a n s ( i + 3 ) a n s ( i + 2 ) a n s ( i + 1 ) ] \left[\begin{array}{cc}\ ans(i+2)&&ans(i+1)&& ans(i) \end{array}\right]\times \left[\begin{array}{cc}\ 1 && 1 &&0 \\ 0 && 0 && 1 \\ 1 && 0 &&0 \end{array}\right] = \left[\begin{array}{cc}\ ans(i+3)&&ans(i+2)&& ans(i+1) \end{array}\right] [ an s ( i + 2 ) an s ( i + 1 ) an s ( i ) ] × 1 0 1 1 0 0 0 1 0 = [ an s ( i + 3 ) an s ( i + 2 ) an s ( i + 1 ) ]
附本题代码 ————————————
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) (((x)>0)?(x):-(x)) const int N = 3000+10; const int MOD = 1e9+7; int n,m,k; const int M = 3; struct Matrix { LL m[M][M]; void clear0(){ for(int i=0;i<M;i++) for(int j=0;j<M;j++) m[i][j]=0; } void clear1(){ for(int i=0;i<M;i++) for(int j=0;j<M;j++) m[i][j]=(i==j); } void display(){ for(int i=0;i<M;i++){ for(int j=0;j<M;j++) printf("%lld ",m[i][j]); puts(""); } puts("------"); } }; Matrix operator * (Matrix &a, Matrix &b){ Matrix c;c.clear0(); for(int k=0;k<M;k++) for(int i=0;i<M;i++) for(int j=0;j<M;j++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD; return c; } Matrix operator ^(Matrix &a,LL b){ Matrix c;c.clear1(); while(b){ if(b&1) c=c*a; b>>=1,a=a*a; } return c; } Matrix a,b; void solve(LL x){ a.clear0();b.clear0(); a.m[0][0]=6,a.m[0][1]=4,a.m[0][2]=3; b.m[0][0]=1,b.m[0][1]=1,b.m[0][2]=0; b.m[1][0]=0,b.m[1][1]=0,b.m[1][2]=1; b.m[2][0]=1,b.m[2][1]=0,b.m[2][2]=0; // b.display(); b=b^(x-2); // b.display(); a=a*b; // a.display(); printf("%lld\n",a.m[0][2]); } int main(){ int _;LL x; scanf("%d",&_); while(_--){ scanf("%lld",&x); solve(x); } return 0; }
I HDU 6031 Innumerable Ancestors ———————————————————————————————————————— 这题是有一棵节点个数为n树,有m次查询, 查询是有两个集合,在集合中分别选出一个元素,求其LCA,问LCA的深度最大是多少
解题思路:
注意数据范围∑ k = 100000 \sum k = 100000 ∑ k = 100000 ,那么就从这里着手么, 显然分别枚举一定不行,所以可以枚举一个集合,对另一个集合,我们可以先进行处理 大概就是进行一个dfs序,然后出现的节点我们就标记一下,这样我就能知道,当前集合的每个节点的子树有没有另一个集合的节点了,
找的时候我们将一个节点不断向上找其父节点,如果这个父节点的子树有另一个集合的元素,那么LCA就是这个父节点
然后注意几个剪枝就好了,
1,采取启发式搜索的思路,将集合内元素及其祖宗节点个数多的标记上去,对另一个小的查找 2,深度小于当前维护的最大值得父节点直接退出就好了, 3,可以先维护下这两个集合内相同元素的深度的最大值,
附本题代码 ——————————————————————————————————
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) (((x)>0)?(x):-(x)) const int N = 100000+10; const int MOD = 1e9+7; int read(){ int x=0;char ch = getchar(); while(ch<'0'||ch>'9') ch = getchar(); while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x; } /************************************************************/ int n,m,k; int sum[N]; # define lowbit(x) (x&-x) void update(int i,int v){for(;i<=n;i+=lowbit(i))sum[i]+=v;} int getSum(int i){int ans=0;for(;i;i-=lowbit(i))ans+=sum[i];return ans;} vector<int >G[N]; int L[N],R[N],fa[N],dep[N],cnt,a[N],b[N],mx,h[N]; void dfs(int u,int f,int d){ dep[u]=d,fa[u]=f;L[u]=++cnt; int gz=G[u].size(); for(int to,i=0;i<gz;i++){ to = G[u][i]; if(to==f) continue; dfs(to,u,d+1); } R[u]=cnt; } void solve(int x){ for(int f=x;f;f=fa[f]){ if(dep[f]<=mx) return ; if(getSum(R[f])-getSum(L[f]-1)>0) mx = max(mx,dep[f]); } } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1,u,v;i<n;i++){ // scanf("%d%d",&u,&v); u=read(),v=read(); G[u].push_back(v); G[v].push_back(u); } cnt=0,dfs(1,0,1); int x;LL ta,tb; for(int i=1;i<=m;i++){ mx=0;ta=tb=0; a[0]=read(); for(int j=1;j<=a[0];j++){ a[j]=read();ta+=dep[a[j]]; h[a[j]]=1; } b[0]=read(); for(int j=1;j<=b[0];j++){ b[j]=read();tb+=dep[b[j]]; if(h[b[j]]) mx=max(mx,dep[b[j]]); } if(tb<ta){ for(int j=1;j<=a[0];j++) update(L[a[j]],1); for(int j=1;j<=b[0];j++) if(dep[b[j]]>mx) solve(b[j]); for(int j=1;j<=a[0];j++) update(L[a[j]],-1); } else { for(int j=1;j<=b[0];j++) update(L[b[j]],1); for(int j=1;j<=a[0];j++) if(dep[a[j]]>mx) solve(a[j]); for(int j=1;j<=b[0];j++) update(L[b[j]],-1); } printf("%d\n",mx); for(int j=1;j<=a[0];j++) h[a[j]]=0; } for(int i=1;i<=n;i++) G[i].clear(); } return 0; }
J HDU 6032 Judicious Strategy ————————————————————————————————————————————————————
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 tabris的博客 ! 赞助
wechat
alipay