第1题 彩票 查看测评数据信息
每张彩票都印有6位数字，如果彩票的前三位数字的和恰好等于后三位数字的和，那么该彩票是"幸运彩票".
输入格式
第一行，一个整数n，表示有n张彩票。1<=n<=1000。
接下来有n行，每行是都印有6位数字。
输出格式
共n行，如果是"幸运彩票"输出"Yes"，否则输出"No"
输入/输出例子1
输入：
5
213132
973894
045207
000000
055776
输出：
Yes
No
Yes
Yes
No
样例解释
无
没什么好说的了
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main()
{
scanf("%d", &n);
while (n--)
{
cin>>s;
if (s[0]-'0'+1+s[1]-'0'+1+s[2]-'0'+1 == s[3]-'0'+1+s[4]-'0'+1+s[5]-'0'+1)
printf("Yes\n");
else printf("No\n");
}
return 0;
}
/*
123456
*/
第2题 路径数量 查看测评数据信息
一个无向图有n个点和m条边。点的编号从1至n，边的编号从1至m。
从S号点出发到达T号点，途中要恰好经过k条边，且必须经过c号结点偶数次，有多少条不同的路径？
答案模998244353。
输入格式
第一行，n,m,k,S,T,c。2<=n<=2000, 1<=m<=2000, 1<=k<=2000, 1<=S,T,c<=n, c != S， c!=T。
接下来是m行，每行两个整数a,b，表示a到b有一条无向边。
输出格式
一个整数。
输入/输出例子1
输入：
4 4 4 1 3 2 1 2 2 3 3 4 1 4
输出：
4
输入/输出例子2
输入：
6 5 10 1 2 3 2 3 2 4 4 6 3 6 1 5
输出：
0
输入/输出例子3
输入：
10 15 20 4 4 6 2 6 2 7 5 7 4 5 2 4 3 7 1 7 1 4 2 9 5 10 1 3 7 8 7 9 1 6 1 2
输出：
952504739
样例解释
样例一解释，有如下4条不同的路径满足条件：
(1, 2, 1, 2, 3)
(1, 2, 3, 2, 3)
(1, 4, 1, 4, 3)
(1, 4, 3, 4, 3)
考虑dp
然后阶段肯定是走过的边数，考虑一下发现，跟边数，哪个点，经过c点数量有密切关系，于是有了这几个状态。
f[i][j][0]表示从1号结点走i条边，到达j号点，且经过c号结点偶数次的路径条数
f[i][j][1]表示从1号结点走i条边，到达j号点，且经过c号结点基数次的路径条数
边界很容易可以得出，f[0][s][0]=1，注意，进过0次c号点也算。
结果也好推，f[k][t][0]
转移方程，i是当前遍历边数，0~k-1（因为i+1会推到k，所以不用到k），x是j点能到的点，k是当前进过c点基数还是偶数：
f[i+1][x][k^(x==c)]+=f[i][j][0]
f[i+1][x][k^(x==c)]+=f[i][j][1]
转移不一定是i -> i+1,也可能是i+1 -> 1且i从小到大！！
#include <bits/stdc++.h>
using namespace std;
const int N=2005, MOD=998244353;
int n, m, k, s, t, c, u1, v1, dp[N][N][2];
vector<int> a[N];
int main()
{
scanf("%d%d%d%d%d%d", &n, &m, &k, &s, &t, &c);
for (int i=1; i<=m; i++)
{
scanf("%d%d", &u1, &v1);
a[u1].push_back(v1);
a[v1].push_back(u1);
}
dp[0][s][0]=1;
for (int i=0; i<k; i++)
for (int j=1; j<=n; j++)
for (int x=0; x<=1; x++)
{
// if (!dp[i][j][k]) continue;
for (auto v : a[j])
dp[i+1][v][x^(v==c)]=(dp[i+1][v][x^(v==c)]+dp[i][j][x])%MOD;
}
printf("%d", dp[k][t][0]);
return 0;
}
标签：输出,d%,int,路径,彩票,断网,Yes,输入 From： https://www.cnblogs.com/didiao233/p/18011408