接下来n行，每行输入n个数，代表区域值（区域值非负）且(1,1)区域值大于零
输入危险值范围1e4
输出描述:
从(1,1)到(n,n)所能经过最小危险值和，若病毒没有可到达消灭点的路，则输出0
示例1
输入
4
1 1 5 0
4 2 1 0
0 4 2 1
5 0 4 2
输出
10
示例2
输入
3
1 0 1
0 1 0
1 1 1
输出
0
备注:
若消灭点(n,n)区域值为0，则也不可被消灭。
思路：dfs+剪枝 / bfs+优先队列 /最短路
虽然数据不是很大，但是dfs不剪枝会wa死。。
代码：
//dfs+剪枝#include
#include
#include
#include
using namespace std;
int a[110][110];
int book[110][110];
int n;
long long int Min=99999999;
int ddd[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int k=0;
void dfs(int x,int y,int step)
{if(step>Min) //就是这一步！没了就wa！很重要！return ;if(x==n&&y==n){k=1;if(stepn||ty<1||ty>n)continue;if(a[tx][ty]!=0&&book[tx][ty]==0){book[tx][ty]=1;dfs(tx,ty,step+a[tx][ty]);book[tx][ty]=0;}}return ;
}
int main()
{memset(book,0,sizeof(book));memset(a,0,sizeof(a));scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);book[1][1]=1;dfs(1,1,a[1][1]);if(k==0)printf("0\n");elseprintf("%d\n",Min);return 0;
}
//bfs+优先队列#include
#include
#include
#include
using namespace std;
int s[105][105],vis[105][105];
int n,ans;
struct node
{int x,y,sum;bool operator <(const node & a) const{return sum>a.sum;}
};
struct position
{int x,y;
};
position dir[4]={{0,1},{1,0},{0,-1},{-1,0}};
int in(int a,int b)
{if(a>0&&b>0&&a<=n&&b<=n&&s[a][b]!=0)return 1;return 0;
}
void BFS(int row,int col)
{priority_queue que;node now,next;now.x=row,now.y=col,now.sum=s[1][1];que.push(now);vis[1][1]=1;while(!que.empty()){now=que.top(); que.pop();if(now.x==n&&now.y==n){ans=now.sum;return ;}for(int i=0;i<4;i++){int x=now.x+dir[i].x,y=now.y+dir[i].y,sum=now.sum;if(in(x,y)&&!vis[x][y]){sum+=s[x][y];next.x=x,next.y=y,next.sum=sum;que.push(next);vis[x][y]=1;}}}
}
int main()
{scanf("%d",&n);memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&s[i][j]);BFS(1,1);printf("min=%d\n",ans);
}
C
younik要挂号
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
younik来到校医院之后打算挂号，校医院最近出台了一个新的挂号制度。医院里有n个专家，专家有一定的挂号费用且挂号费用是一个从1到m的整数，younik别出心裁，打算选择n个专家进行挂号，并把这n个专家的挂号费用排成一个序列a。
求满足下列条件的长度为n的序列a的个数
1. 该序列包含n个专家的挂号费用；
2. 对于每一个序列，有且仅有一对相同的元素；
3. 对于每一个序列，存在一个位置i，使得位置i之前的挂号费用严格递增，位置i之后的挂号费用严格递减，即a[j]a[j+1](j>=i)。
输入描述:
输入包含一行，一行内有两个整数，分别是n和m（2≤\leq≤n≤\leq≤m≤\leq≤2×\times×105）。
输出描述:
输出一个整数，即为满足条件的序列a的个数，由于数目过大，需要对998244353取模。
示例1
输入
3 4
输出
6
说明
满足条件的序列有6个，分别是[1,2,1]、[1,3,1]、[1,4,1]、[2,3,2]、[2,4,2]、[3,4,3]
示例2
输入
3 5
输出
10
思路：组合数学的问题。
对于一个序列，先确定要选哪些数字，所以是Cm n-1（这里其实有点不懂为啥是n-1，后面同理），然后再确定哪个数去作为重复数字（很显然除了最大值，其他的都能是重复的），有n-2种选择。如果已经确定了其中的数字，那么能够肯定的是：“相同的数字在最大的数字的两边”，不妨以最大数字为界限，划分为左右两部分数字，而重复的那2个数字肯定是在最大数字的两边的，那么现在还剩下的数字个数为n-3，且没有重复的数字，那么很显然每个数只有两个选择，要么是最大数的左边，要么右边，共有2^(n-3)个选择（注意这里已经不用考虑给左边或右边的数字排序了，分完就是有序的）。
综上所述，答案为Cm n-1 *2^(n-3) *（n-2）（当n==2时，必定无解，输出0）
因为组合数模数过大，所以注意使用乘法逆元。
代码：
#include
using namespace std;
typedef long long ll;ll mod = 998244353;ll quick_pow(ll a,ll b)
{//快速幂，求a^b ll ans = 1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
ll multi(ll m)
{ //求 m!%modll ans=1;for(int i=2;i<=m;i++)ans=ans*i%mod;return ans%mod;
}/*ll inv(ll a)
{ //求a模mod状态下的逆元 return quick_pow(a,mod-2)%mod;
}*/int main()
{ll n,m;cin>>n>>m;if(n<3) cout<<0;else { ll ans1 = multi(n-1)*multi(m-n+1)%mod;//求阶乘 ll ans2 = quick_pow(2,n-3)%mod;ans1 = multi(m)*quick_pow(ans1,mod-2)%mod; //求逆元 ll ans = ans1%mod*ans2%mod*(n-2)%mod;cout<
D
younik要排号
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Younik挂好号之后，就去找医生了。但是她没想到，看医生居然也要排队！
于是younik可怜兮兮地站在大厅里，盯着墙上的显示屏，显示屏会不停地打出名字，如果一个人被叫到但没进去，显示屏可能会叫他很多次。
你能告诉younik她是第几个被叫到的人吗？
Ps.如果一个人被叫了两次，他还是一个人，不能算两个人。（题目数据范围为200）
输入描述:
第一行是一个正整数n，表示显示屏会叫几次。
接下来n行，每行都是一个名字。
输出描述:
一个正整数，表示younik是第几个被叫到的人。不需要换行。
示例1
输入
6
zhangsan
lisi
wangwu
lisi
younik
liliu
输出
4
思路：这个是签到题，就是去一下冲，set最好用，但是当时突然没想到set（用的太少233，然后用了map，也可，但是map我写的很鸡肋，看了其他大佬的代码，map写的非常清晰。但不管咋说，都能写。
代码：
//自己的鸡肋代码#include using namespace std;int main()
{int n;char str[101][101];int len[101];int flag[101];cin>>n;int tt;for(int i=1;i<=n;i++){cin>>str[i];len[i]=1;flag[i]=0;if(strcmp(str[i],"younik")==0){tt=i;}}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(strcmp(str[i],str[j])==0){len[i]++;flag[i]=1;}}}int sum=0;for(int i=1;i<=tt;i++){if(len[i]==1)sum++;}printf("%d\n",sum);return 0;
}
//set#include using namespace std;int main()
{int T; cin>>T;set st;int ans=0;while(T--) {string s; cin>>s;st.insert(s);if(s=="younik"){ans=st.size();}} printf("%d\n",ans);return 0;
}
//比较好看的map#include using namespace std;int main()
{mapq;int T;cin>>T;int x=0;int ans=0;while(T--){string s;cin>>s;q[s]++;if(q[s]==1){x++;}if(s=="younik"){ans=x;}}cout<
F
新冠病毒要回家
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
新冠病毒被医生从患者的身体中赶了出来，它很伤心，原本一切都是那么的快乐，它和它的孩子们快乐地生活在一起。但是这里的抗疫力度太强了，被赶出来后，由于人们都带了口罩，它没办法再次回到之前那样的舒适环境。现在它想要离开医院回家。它有很多条路可以离开医院，虽然它想要尽可能快的回去，但是它还想看看路上的其它病毒过得怎么样，也好顺便带它们一起离开，于是它决定走第二短的路回去。医院总有 V (0 ~ V-1) 个路口，这些路口之间有 E 条路连接。新冠病毒现在在第 0 个路口，第 V-1 个路口就是医院出口。保证有路可以离开。
第二短路是严格第二短（小于最短路），保证路径存在，路径可以重复走。
输入描述:
第一行：两个空格隔开的整数 V 和 E 。( 1 <= V <= 5000 )，( 0 <= E <= 100000 ) 。
第二行开始有 E 行：每行包含 3 个空格隔开的整数 a、b、d 。表示路口 a 和 b 之间有一条长度为 d 的路。( 0 <= a,b < V )，( 0 < d <= 5000 ) 。
输出描述:
输出占一行：从路口 0 到 路口 V-1 的第二短的路径长度。
示例1
输入
4 4
0 1 100
1 3 200
1 2 250
2 3 100
输出
450
示例2
输入
2 1
0 1 100
输出
300
说明
路径可以重复走
思路：次短路问题，直接上板子就能过，而且这个是双向的，第一次写成了单向的结果wa了，改成双就对了
代码：
//链式前向星#include
using namespace std;
typedef long long ll;
typedef pair iip;
typedef pair llp;
const int MAXN=100005;
const int MAXM=100005;
const int INF=0x3f3f3f3f;int n,m;
int a,b,d;
int dis[MAXN],dis2[MAXN];
int cnt,head[MAXN];
struct edge
{int u;int v;int w;int next;edge(){};edge(int _u,int _v,int _w,int _next):u(_u),v(_v),w(_w),next(_next){};
}e[2*MAXM];void init()
{cnt=0;for(int i=0;i<=n;i++) {dis[i]=INF;dis2[i]=INF;head[i]=-1;}
}void addEdge(int u,int v,int w)
{e[cnt]=edge(u,v,w,head[u]);head[u]=cnt++;
}void dij(int s)
{dis[s]=0;priority_queue,greater > pq;pq.push({dis[s],s});while(!pq.empty()) {iip now=pq.top();pq.pop();int u=now.second;int d=now.first;if(dis2[u]d2) {swap(dis[v],d2);pq.push({dis[v],v});}if(dis2[v]>d2&&dis[v]
//vector+pair#include
#include
#include
#include
#include
using namespace std;const int MAX_V = 5000;
const int MAX_E = 100000;
const int INF = INT_MAX / 2;typedef pair Edge; // 路径长度、点vector G[MAX_V]; // 邻接表
int dist[MAX_V]; // 从源点到其它点的最短距离
int dist2[MAX_V]; // 次短路
int V, E; // 节点数、路径数void inputs()
{scanf("%d %d", &V, &E);int A, B, D;for (int i=0; i < E; ++ i){scanf("%d %d %d", &A, &B, &D);G[A].push_back(make_pair(D, B));G[B].push_back(make_pair(D, A));}
}int dijkstra(int s)
{priority_queue, greater > que;fill(dist, dist + V, INF);fill(dist2, dist2 + V, INF);dist[s] = 0;que.push(make_pair(0, s));while (!que.empty()){Edge e = que.top();que.pop();int v = e.second;int d = e.first;if (dist2[v] < d)continue;for (int i=0; i < G[v].size(); ++ i){e = G[v][i];int d2 = d + e.first;if (dist[e.second] > d2){swap(dist[e.second], d2);que.push(make_pair(dist[e.second], e.second));}if (dist2[e.second] > d2 && dist[e.second] < d2){dist2[e.second] = d2;que.push(make_pair(dist2[e.second], e.second));}}}return dist2[V - 1];
}int main()
{inputs();int res = dijkstra(0);printf("%d\n", res);return 0;
}
G
younik吃大餐
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Younik的检查结果出来了，核酸检测为阴性，她非常高兴，立刻决定去饭店大吃一顿。到了饭店，Younik看到琳琅满目的菜单，开始犯了选择困难症。这时作为顶级吃货的你恰好坐到了Younik的旁桌，你决定发扬一下雷锋精神，帮助Younik决定吃哪些菜。假设每一道菜都有相应的快乐值，Younik每吃一道菜就会获得相应的快乐值，这里有N道菜，每道菜可以吃多次，但是同一道菜每重复吃一次，得到的快乐值会比原来的快乐值少 2^(k-1) 点（k为重复吃的次数，第一次重复，得到的快乐值会比这道菜的原快乐值少1点，重复第二次时少2点，以此类推）。现在Younik的钱包中有M元，你觉得她可以得到的最大的快乐值是多少呢？
输入描述:
第一行输入N M，表示共有N道菜，小明有M元。接下来的N行，每行有两个数字Wi,Vi，第一个数字表示吃这道菜可得到的快乐值，第二个数字表示这道菜的价格。
菜的标号从1开始。
输出描述:
输出所能得到的最大快乐值
示例1
输入
6 9
3 2
5 2
2 7
1 2
3 3
6 3
输出
18
备注:
0 < N ≤ 100
0 < Vi,Wi ≤ 100
0 < M ≤ 10000
思路：可以看成就是一个加了一步的完全背包问题
代码：
#includeusing namespace std;const int maxn=1e5+5;int n,m;
int w[maxn],v[maxn];
int dp[maxn];int main()
{cin>>n>>m;int idx=0;for(int i=0;i>ww>>vv;w[idx]=ww;v[idx]=vv;idx++;int k=1;while(ww-pow(2,k-1)>0){w[idx]=ww-pow(2,k-1);v[idx]=vv;idx++;k++;}} //上面的部分我是理解成把一个物品的价值拆开，因为每次重选一个物品的时候，价值都会发生变化，不妨把这些不同价值的同一个物品看成是不同的物品，idx表示现在所有不同价值的物品，来代替nfor(int i=0;i=v[i];j--){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}printf("%d\n",dp[m]);return 0;
}
