河南省交通基本建设质量检测监督站网站,杨中市网站建设,中国勘察设计行业信息化建设网站,软件技术专科有出路吗题目详情 - L2-041 插松枝 (pintia.cn)
思路#xff1a;模拟
背包就是个栈#xff0c;开个stack解决流程思路是#xff0c;每次取推进器前#xff0c;尽可能拿背包的#xff0c;背包拿到不可以时#xff0c;跳出拿推进器时判断#xff1a; 如果背包装得下#xff0c;…题目详情 - L2-041 插松枝 (pintia.cn)
思路模拟
背包就是个栈开个stack解决流程思路是每次取推进器前尽可能拿背包的背包拿到不可以时跳出拿推进器时判断 如果背包装得下装入背包。往下继续装不下判断能不能插不可以换树枝。重新检查
#include bits/stdc.h
using namespace std;
#define ll long long
typedef unsigned long long ull;
typedef pairlong long, long long pll;
typedef pairint, int pii;//double 型memset最大127最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF 0x3f3f3f3f; //int型的INF
const ll llINF 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N 1e3 10;int a[N];
vectorintans[N];
stackintb;
int main()
{int n,m,k;cinnmk;for (int i1; in; i)cina[i];int maxnINF,p1;for (int i1; in; i){while ((int)b.size()0)//先拿背包{if (maxnb.top()){ans[p].push_back(b.top());maxnb.top();b.pop();if ((int)ans[p].size()k){p,maxnINF;}}else break;}if ((int)b.size()m){if (a[i]maxn)//能插就插入{ans[p].push_back(a[i]);maxna[i];if ((int)ans[p].size()k){p,maxnINF;}}else//不行i保持下一次还是这里换树枝{p,maxnINF,i--;}}else if ((int)b.size()m)//背包有空间直接放{b.push(a[i]);}}while ((int)b.size()0){if (maxnb.top()){ans[p].push_back(b.top());maxnb.top();b.pop();if ((int)ans[p].size()k){p,maxnINF;}}else{p,maxnINF;}}for (int i1; ip; i)for (int j0; j(int)ans[i].size(); j){coutans[i][j];if (j(int)ans[i].size()-1)coutendl;else cout ;}return 0;
}
题目详情 - L2-043 龙龙送外卖 (pintia.cn)
思路画图模拟dfs 假设我们需要到达上图蓝色点显然绿色边都需要遍历。因为每次点与点转移所以一条路径走2次且最多两次我们保证最优是这条路径走过一次来回就不会再走。当然我们到达最后一个点时不需要回去或者去其他点那么我们在最深处不回去不用走两遍的边显然是最多为最优解。
我们设起点深度为0
#include bits/stdc.h
using namespace std;
#define ll long long
typedef unsigned long long ull;
typedef pairlong long, long long pll;
typedef pairint, int pii;//double 型memset最大127最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF 0x3f3f3f3f; //int型的INF
const ll llINF 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N 1e5 10;int dep[N],head[N],f[N];
int num;
bool vis[N];//每条边只走一次
struct node
{int next,to;
} edge[N];void add(int u,int v)
{edge[num].nexthead[u];edge[num].tov;head[u]num;
}void dfs(int u,int fa)//建立深度
{dep[u]dep[fa]1;for (int ihead[u]; i; iedge[i].next){int vedge[i].to;if (v!fa)dfs(v,u);}
}int main()
{int n,m,st,x;cinnm;for (int i1; in; i){cinx;f[i]x;if (x-1)sti;add(x,i);}dep[0]-1;dfs(st,0);int maxn0;//记录走过点的最深层ll ans0;//ans记录至少需要走的边数*2vis[st]1;//从起点出发肯定是访问过while (m--){cinx;maxnmax(maxn,dep[x]);while (!vis[x]){ans2;vis[x]1;xf[x];}coutans-maxnendl;}
}题目详情 - L2-044 大众情人 (pintia.cn)
思路最短路
因为需要建立所有人之间的最短路又因为数据是,之间floyd就可最短路径三大算法——1弗洛伊德算法floyd注意题目要求所有异性所以不认识也要算距离无穷大
#include bits/stdc.h
using namespace std;
#define ll long long
typedef unsigned long long ull;
typedef pairlong long, long long pll;
typedef pairint, int pii;//double 型memset最大127最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF 0x3f3f3f3f; //int型的INF
const ll llINF 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N 5e2 10;int dis[N][N];
bool sex[N];//标记性别0为男1为女int main()
{int n,k,x,d;char c;cinn;memset(dis,0x3f,sizeof(dis));//初始无穷大for (int i1; in; i){cinck;if (cF)sex[i]1;else sex[i]0;while (k--){cinxcd;dis[i][x]min(d,dis[i][x]);}}//floydfor (int k1; kn; k)for (int i1; in; i)for (int j1; jn; j)if (i!j)dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);vectorintf,m;int fdINF,mdINF;//大众情人的离他最远异性距离for (int i1; in; i){int maxn0;//记录离i最远的异性for (int j1; jn; j){if (sex[i]^sex[j]) //异或为真性别不同{maxnmax(maxn,dis[j][i]);//j到i的距离不是i到j是其他人对i}}if (sex[i])//女性{if (maxnfd){fdmaxn;f.clear();f.push_back(i);}else if (maxnfd)f.push_back(i);}else{if (maxnmd){mdmaxn;m.clear();m.push_back(i);}else if (maxnmd)m.push_back(i);}}for (int i0; i(int)f.size(); i){coutf[i];if (i(int)f.size()-1)coutendl;else cout ;}for (int i0; i(int)m.size(); i){coutm[i];if (i(int)m.size()-1)coutendl;else cout ;}return 0;
}题目详情 - L3-031 千手观音 (pintia.cn)
思路拓扑排序
拓扑排序
每次如果前后两个字符串位数相同比较第一个不同的位置注意题目的字典序最小是基于你所有确定的排完序后再确定的所以我们必须建立小值到大值的边而不是反过来。这样拓扑时是不断确定最小位的而为确定的位置也始终是从能不能放在低位考虑而不是上来就因为入度0放最高位。按照字典序升序排那么我们需要建立小点到大点的边然后跑最小堆。不能反过来建反向边跑最大堆这样你就不能保证是尽量让值小的排前面的前提下建字典序。如存在d-a,c如果最小堆答案是c.d.a,如果反向最大堆写出来是d.a.c因为一开始入度0只有a与c因为我们只需要查找所以开无序map比较快map有可能寄。
#include bits/stdc.h
using namespace std;
#define ll long long
typedef unsigned long long ull;
typedef pairlong long, long long pll;
typedef pairint, int pii;//double 型memset最大127最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF 0x3f3f3f3f; //int型的INF
const ll llINF 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N 1e5 10;unordered_mapstring,intmp;
string back[N];
int in[N];
int head[N],num;
struct node
{int next,to;
} edge[N];
void add(int u,int v)
{edge[num].nexthead[u];edge[num].tov;head[u]num;
}int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n,cnt0;cinn;string s,tmp;vectorstringb;while (n--){vectorstringa;cins;s.;int len0;//记录片段长度for (int i0; i(int)s.size(); i){if (s[i].){tmps.substr(i-len,len);if (!mp[tmp])mp[tmp]cnt,back[cnt]tmp;a.push_back(tmp);len0;}else len;}if ((int)a.size()(int)b.size()) //如果前后字符串相同{for (int j0; j(int)a.size(); j){if (a[j]!b[j]){add(mp[b[j]],mp[a[j]]);in[mp[a[j]]];break;}}}ba;}vectorstringans;priority_queue pairstring,int,vector pairstring,int ,greaterpairstring,int q;for (int i1; icnt; i)if (!in[i])q.push({back[i],i});while (!q.empty()){auto uq.top();q.pop();ans.push_back(u.first);for (int ihead[u.second]; i; iedge[i].next){int vedge[i].to;if (--in[v]0)q.push({back[v],v});}}for (int i0; i(int)ans.size(); i){coutans[i];if (i(int)ans.size()-1)coutendl;else cout.;}return 0;
}
题目详情 - L3-032 关于深度优先搜索和逆序对的题应该不会很难吧这件事 (pintia.cn) 思路
假设uv,我们讨论他们在树上的位置 如果u是v的祖先显然他们构成一对逆序对那么在所有dfs序里面他们都能有贡献为dfs序排列数如果u是v儿子那么他们永远不构成逆序对那么在所有dfs序里面他们都没有贡献其他情况那么在到达u与v的lca时如果从lca先去u那么u与v构成逆序对否则不行。所以他的贡献是1/2dfs序的排列数。显然计算出每个点的祖先比他大的数量与儿子比他大的数量就能得到结果。然而复杂度是O),所以我们可以在遍历树的时候用树状数组维护当前树上深入路径时比当前点u大的数量那么他们就是贡献1的祖先还有比u小的点的数量显然u是比他们大的值且是他们的儿子永远构成不了贡献。树状数组dfs序数量显然是每个点儿子排列的乘积
#include bits/stdc.h
using namespace std;
#define ll long long
#define int ll//全部开成ll
const int N 3e5 10;
const int mod1e97;
int n,num;
int t[N],head[N],dp[N],pre[N];
int cnt1,cnt2;//分别记录一直有贡献的逆序对数量与一直没贡献的逆序对数量
struct node
{int next,to;
} edge[N1];void add(int u,int v)
{edge[num].nexthead[u];edge[num].tov;head[u]num;
}void updateadd(int x,int k)
{for (int ix; in; ii-i)t[i](t[i]k)%mod;
}ll ask(int x)
{ll ans0;for (int ix; i; i-i-i)ans(anst[i])%mod;return ans;
}ll fastpower(ll base,ll power)
{ll ans1;while (power){if (power1)ansans*base%mod;power1;basebase*base%mod;}return ans;
}void dfs(int u,int fa)
{dp[u]1;int cnt0;//记录亲儿子数量for (int ihead[u]; i; iedge[i].next){int vedge[i].to;if (v!fa){cnt;cnt1(cnt1ask(n)-ask(v)mod)%mod;//有减法的取模记得加mod保证正数cnt2(cnt2ask(v-1))%mod;updateadd(v,1);//把当前点加入树状数组后继续深入dfs(v,u);updateadd(v,-1);//出来后从树状树状删除dp[u]dp[u]*dp[v]%mod;}}dp[u]dp[u]*pre[cnt]%mod;//dp为组合数
}int32_t main()
{int r,x,y;cinnr;pre[0]1;for (int i1; in; i)pre[i]pre[i-1]*i%mod; //预处理排列数for (int i1; in; i){cinxy;add(x,y),add(y,x);}updateadd(r,1);//显然根节点一直在树状数组dfs(r,0);int num(n*(n-1)%mod*fastpower(2,mod-2)%mod-cnt2mod)%mod;//贡献为1/2的点,即n*(n-1)/2-cnt2,当然是包括cnt1的但是只算了cnt1一半的贡献后面cnt1还有自己算另一半ll ans(num*dp[r]%mod*fastpower(2,mod-2)%modcnt1*dp[r]%mod*fastpower(2,mod-2)%mod)%mod;coutansendl;return 0;
}
文章转载自： http://www.morning.nrpp.cn.gov.cn.nrpp.cn http://www.morning.xdhcr.cn.gov.cn.xdhcr.cn http://www.morning.hmwjk.cn.gov.cn.hmwjk.cn http://www.morning.bftqc.cn.gov.cn.bftqc.cn http://www.morning.hgwsj.cn.gov.cn.hgwsj.cn http://www.morning.qjrjs.cn.gov.cn.qjrjs.cn http://www.morning.fsnhz.cn.gov.cn.fsnhz.cn http://www.morning.bpmfr.cn.gov.cn.bpmfr.cn http://www.morning.kqbjy.cn.gov.cn.kqbjy.cn http://www.morning.tfwsk.cn.gov.cn.tfwsk.cn http://www.morning.bpmmq.cn.gov.cn.bpmmq.cn http://www.morning.wjzzh.cn.gov.cn.wjzzh.cn http://www.morning.wjhqd.cn.gov.cn.wjhqd.cn http://www.morning.cnqff.cn.gov.cn.cnqff.cn http://www.morning.muzishu.com.gov.cn.muzishu.com http://www.morning.cnhgc.cn.gov.cn.cnhgc.cn http://www.morning.sjgsh.cn.gov.cn.sjgsh.cn http://www.morning.wmpw.cn.gov.cn.wmpw.cn http://www.morning.zhnyj.cn.gov.cn.zhnyj.cn http://www.morning.fchkc.cn.gov.cn.fchkc.cn http://www.morning.hdzty.cn.gov.cn.hdzty.cn http://www.morning.gqjqf.cn.gov.cn.gqjqf.cn http://www.morning.crkmm.cn.gov.cn.crkmm.cn http://www.morning.pclgj.cn.gov.cn.pclgj.cn http://www.morning.rknsp.cn.gov.cn.rknsp.cn http://www.morning.sjbpg.cn.gov.cn.sjbpg.cn http://www.morning.qjlnh.cn.gov.cn.qjlnh.cn http://www.morning.jllnh.cn.gov.cn.jllnh.cn http://www.morning.pzqnj.cn.gov.cn.pzqnj.cn http://www.morning.tmnyj.cn.gov.cn.tmnyj.cn http://www.morning.wtyqs.cn.gov.cn.wtyqs.cn http://www.morning.lxmks.cn.gov.cn.lxmks.cn http://www.morning.ksggl.cn.gov.cn.ksggl.cn http://www.morning.nxdqz.cn.gov.cn.nxdqz.cn http://www.morning.lizimc.com.gov.cn.lizimc.com http://www.morning.xfwnk.cn.gov.cn.xfwnk.cn http://www.morning.qqfcf.cn.gov.cn.qqfcf.cn http://www.morning.gwqcr.cn.gov.cn.gwqcr.cn http://www.morning.lnbyk.cn.gov.cn.lnbyk.cn http://www.morning.nzcgj.cn.gov.cn.nzcgj.cn http://www.morning.mqss.cn.gov.cn.mqss.cn http://www.morning.xsjfk.cn.gov.cn.xsjfk.cn http://www.morning.mwrxz.cn.gov.cn.mwrxz.cn http://www.morning.npmpn.cn.gov.cn.npmpn.cn http://www.morning.gfqjf.cn.gov.cn.gfqjf.cn http://www.morning.gchqy.cn.gov.cn.gchqy.cn http://www.morning.mynbc.cn.gov.cn.mynbc.cn http://www.morning.mrnnb.cn.gov.cn.mrnnb.cn http://www.morning.vvbsxm.cn.gov.cn.vvbsxm.cn http://www.morning.sflnx.cn.gov.cn.sflnx.cn http://www.morning.qzqfq.cn.gov.cn.qzqfq.cn http://www.morning.mkpkz.cn.gov.cn.mkpkz.cn http://www.morning.xqndf.cn.gov.cn.xqndf.cn http://www.morning.qsy40.cn.gov.cn.qsy40.cn http://www.morning.gyfwy.cn.gov.cn.gyfwy.cn http://www.morning.hgsylxs.com.gov.cn.hgsylxs.com http://www.morning.fglzk.cn.gov.cn.fglzk.cn http://www.morning.xbkcr.cn.gov.cn.xbkcr.cn http://www.morning.fykqh.cn.gov.cn.fykqh.cn http://www.morning.rbnnq.cn.gov.cn.rbnnq.cn http://www.morning.yhplt.cn.gov.cn.yhplt.cn http://www.morning.lqklf.cn.gov.cn.lqklf.cn http://www.morning.mbdbe.cn.gov.cn.mbdbe.cn http://www.morning.lflsq.cn.gov.cn.lflsq.cn http://www.morning.jzyfy.cn.gov.cn.jzyfy.cn http://www.morning.27asw.cn.gov.cn.27asw.cn http://www.morning.ygwbg.cn.gov.cn.ygwbg.cn http://www.morning.tstwx.cn.gov.cn.tstwx.cn http://www.morning.pbpcj.cn.gov.cn.pbpcj.cn http://www.morning.yfmlj.cn.gov.cn.yfmlj.cn http://www.morning.qxrct.cn.gov.cn.qxrct.cn http://www.morning.jntdf.cn.gov.cn.jntdf.cn http://www.morning.fndmk.cn.gov.cn.fndmk.cn http://www.morning.ypnxq.cn.gov.cn.ypnxq.cn http://www.morning.zhnyj.cn.gov.cn.zhnyj.cn http://www.morning.mpngp.cn.gov.cn.mpngp.cn http://www.morning.zbjfq.cn.gov.cn.zbjfq.cn http://www.morning.huxinzuche.cn.gov.cn.huxinzuche.cn http://www.morning.fglyb.cn.gov.cn.fglyb.cn http://www.morning.qkqjz.cn.gov.cn.qkqjz.cn
