传送门：https://ac.nowcoder.com/acm/contest/5666#question
F. Infinite String Comparision
题意：
比较两个字符串无穷次循环形成的字符串的大小
思路：
把较长的一个字符串变为两倍，较短的一个字符串补齐，使处理后的俩字符串等长。比较这两个字符串即可
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10;
int main()
{
string a, b;
while(getline(cin, a))
{
getline(cin, b);
int len1 = a.size();
int len2 = b.size();
bool flag = 0;
if(len1 > len2)
{
flag = 1;
string tmp = b;
b = a;
a = tmp;
swap(len1, len2);
}
b += b;
for(int i = len1; i < 2 * len2; ++i)
{
a += a[(i - len1) % len1];
}
if(a < b)///a < b
{
if(!flag)
cout<<"<"<<'\n';
else
cout<<">"<<'\n';
}
else if(a>b)///a > b
{
if(!flag)
cout<<">"<<'\n';
else
cout<<"<"<<'\n';
}
else
cout<<"="<<'\n';
}
return 0;
}I. 1 or 2
题意：
现有一个 n 个点 m 条边的无向图，给出每个节点的目标度数，问原图中是否存在满足目标度数的一个子图
思路：
原题hdu 3551，用了带花树开花来求一般图的最大匹配，主要是建图，把 每个点 小于等于 指定度数 的度数 都拆成一个点，每条边也拆成两个点，具体讲解见：https://www.cnblogs.com/xiongtao/p/11189452.html
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int MAXN = 1e3 + 5;
int N, M; //点的个数，点的编号从 1 到 N
bool Graph[MAXN][MAXN];
int Match[MAXN];
bool InQueue[MAXN],InPath[MAXN],InBlossom[MAXN];
int Head,Tail;
int Queue[MAXN];
int Start,Finish;
int NewBase;
int Father[MAXN],Base[MAXN];
int Count;//匹配数，匹配对数是 Count/2
int d[MAXN], mp[MAXN][MAXN], tot, x[MAXN], y[MAXN];
void CreateGraph()
{
tot = 0;
memset(Graph, false, sizeof(Graph));
for(int i = 1; i <= N; ++i)
{
for(int j = 1; j <= d[i]; ++j)
{
mp[i][j] = ++tot;
}
}
for(int i = 1; i <= M; ++i)
{
for(int j = 1; j <= d[x[i]]; ++j)
Graph[mp[x[i]][j]][tot + 1] = Graph[tot + 1][mp[x[i]][j]] = 1;
for(int j = 1; j <= d[y[i]]; ++j)
Graph[mp[y[i]][j]][tot + 2] = Graph[tot + 2][mp[y[i]][j]] = 1;
Graph[tot + 1][tot + 2] = Graph[tot + 2][tot + 1] = 1;
tot += 2;
}
}
void Push(int u)
{
Queue[Tail] = u;
Tail++;
InQueue[u] = true;
}
int Pop()
{
int res = Queue[Head];
Head++;
return res;
}
int FindCommonAncestor(int u,int v)
{
memset(InPath,false,sizeof(InPath));
while(true)
{
u = Base[u];
InPath[u] = true;
if(u == Start)
break;
u = Father[Match[u]];
}
while(true)
{
v = Base[v];
if(InPath[v])
break;
v = Father[Match[v]];
}
return v;
}
void ResetTrace(int u)
{
int v;
while(Base[u] != NewBase)
{
v = Match[u];
InBlossom[Base[u]] = InBlossom[Base[v]] = true;
u = Father[v];
if(Base[u] != NewBase)
Father[u] = v;
}
}
void BloosomContract(int u,int v)
{
NewBase = FindCommonAncestor(u,v);
memset(InBlossom,false,sizeof(InBlossom));
ResetTrace(u);
ResetTrace(v);
if(Base[u] != NewBase)
Father[u] = v;
if(Base[v] != NewBase)
Father[v] = u;
for(int tu = 1; tu <= tot; tu++)
if(InBlossom[Base[tu]])
{
Base[tu] = NewBase;
if(!InQueue[tu])
Push(tu);
}
}
void FindAugmentingPath()
{
memset(InQueue,false,sizeof(InQueue));
memset(Father,0,sizeof(Father));
for(int i = 1; i <= tot; i++)
Base[i] = i;
Head = Tail = 1;
Push(Start);
Finish = 0;
while(Head < Tail)
{
int u = Pop();
for(int v = 1; v <= tot; v++)
if(Graph[u][v] && (Base[u] != Base[v]) && (Match[u] != v))
{
if((v == Start) || ((Match[v] > 0) && Father[Match[v]] > 0))
BloosomContract(u,v);
else if(Father[v] == 0)
{
Father[v] = u;
if(Match[v] > 0)
Push(Match[v]);
else
{
Finish = v;
return;
}
}
}
}
}
void AugmentPath()
{
int u,v,w;
u = Finish;
while(u > 0)
{
v = Father[u];
w = Match[v];
Match[v] = u;
Match[u] = v;
u = w;
}
}
void Edmonds()
{
memset(Match,0,sizeof(Match));
for(int u = 1; u <= tot; u++)
{
if(Match[u] == 0)
{
Start = u;
FindAugmentingPath();
if(Finish > 0)
AugmentPath();
}
}
}
void PrintMatch()
{
Count = 0;
for(int u = 1; u <= tot; u++)
if(Match[u] > 0)
Count++;
// cout<<Count<<' '<<tot<<'\n';
if(Count == tot)
cout<<"Yes"<<'\n';
else
cout<<"No"<<'\n';
}
int main()
{
int u, v;
while(~scanf("%d%d", &N, &M))
{
for(int i = 1; i <= N; ++i)
scanf("%d", &d[i]);
for(int i = 1; i <= M; ++i)
scanf("%d%d", &x[i], &y[i]);
CreateGraph();//建图
Edmonds();//进行匹配
PrintMatch();//输出匹配数和匹配
}
return 0;
}J. Easy Integration
题意：
给 n ，求
思路：
n = 1，ans = 1 /（2 * 3）；
n = 2，ans = (1 * 2) / (3 * 4 * 5);
n = 3，ans = (1 * 2 * 3) / (4 * 5 * 6 * 7);
.....................
推导见https://blog.csdn.net/qq_44607936/article/details/107308777?%3E
这个是沃利斯积分的一个结论，接下来打个阶乘的表，费马小定理和快速幂求逆元就完了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 2e6 + 10;
ll fac[N], inv[N];
ll qpow(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b & 1)
ans = ans * a % mod;
a = a * a % mod;
b /= 2;
}
return ans % mod;
}
void init()
{
fac[0] = 1;
for(int i = 1; i < N; ++i)
{
fac[i] = fac[i - 1] * i % mod;
inv[i] = qpow(fac[i], mod - 2);
}
}
int main()
{
init();
ll n;
while(~scanf("%lld", &n))
{
ll ans = qpow((((fac[2 * n + 1] % mod) * (inv[n] % mod)) % mod * (inv[n] % mod)) % mod, mod - 2) % mod;
cout<<ans<<'\n';
}
return 0;
}
京公网安备 11010502036488号