The 15th Jilin Provincial Collegiate Programming Contest(补题)
这次只做了4个题，感觉自己还有很多不足，加油ヾ(◍°∇°◍)ﾉﾞ
这次发现好多题都需要cin加速器，好多题不加这个都会超时
补了四个题
B
这个题我一开始以为很简单，以为就是普通的除法，然后发现小数点后的数位既然有1e3之多，就觉得这个题不简单了，可是我之前也没做过模拟除法的题（还是自己太菜），然后一筹莫展
其实这个就是模拟除法，我们需要小数点后的k+1位，（我们需要最后一位判断是舍还是入（四舍五入））
具体看代码
#include <iostream>
#include <vector>
using namespace std;
#define int long long
int a,b,k;
void solve()
{
cin>>a>>b>>k;
vector<int>ans(1,a/b);
int c=a%b;
for (int i=1;i<=k+1;i++)//我觉得这一段是模拟除法的关键代码
{
c=c*10;
ans.push_back(c/b);
c%=b;
}
if (ans[k+1]>=5)//判断是否进位
{
ans[k]++;
}
int r=k;
while (ans[r]>=10&&r>0)//防止进位会导致前面的一位还需要进位
{
ans[r]%=10;
ans[r-1]++;
r--;
}
cout<<ans[0]<<".";
for (int i=1;i<=k;i++)
{
cout<<ans[i];
}
return ;
}
signed main ()
{
int t;
// cin>>t;
t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
G
这个题目大意是给我们一个nXn的矩阵，但是是残缺的，这个矩阵本来是由0和1组成的矩阵，但是他是残缺的（存在一些位置的是-1），而我们需要的补齐这些残缺的位置，判断它是1还是0，但是需要满足一些条件，要在补充完成后满足题目中给的行异或值和列异或值，而且一定是只有一个情况（不可以存在多种情况）
一开始是没什么思路（我没有思路）
然后看了大佬们的题解，发现有大佬是用拓扑排序的方法解题的
还有一个小细节：我们还需要求不完整的矩阵的行列的异或值，如果这一行还有不完整的（这里用拓扑的入度不为1，当(i，j)是不完整的，那么i会入度加一，j+n(列用j+n表示，这样比较方便，而且不会和行撞在一起)，因为入度为0的一定是完整的，那么只有在入度为1的时候那一个缺失的位置的值才能确定，我们需要像拓扑排序一样一个一个找（不过我们这个是入度为1的加入队列，而且还需要更新此时的行列异或值，以及一些位置的值）
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <queue>
using namespace std;
vector<int>in,xo,res;//xo是此时的行列异或情况，如果i>n那么是表示列，否者是代表行
vector<vector<int>>e,ans;
int n;
void change (int x,int y)//更新这一个位置的值，只要有入度，那么x和y(大的是列，小的是行)这一个位置一定是残缺的
{
int c=xo[x]^res[x];//满足x行的要求，x,y是c,x，y其中一定有一个是行，一个是列（这也很方便，不用在这里判断是行还是列，放真这个残缺的值一定是xo[x]^res[x](c),此时的情况(xo[x])和要求(res[x])一样，那么这个位置的值是0，否则是1，x已经是好的了，
xo[y]^=c;//和x相连的情况也会有影响
int h=min(x,y);
int l=max(x,y)-n;
ans[h][l]=c;//把x，l-n的位置变成c
return ;
}
void solve()
{
cin>>n;
queue<int>q;
e=vector<vector<int>>(n<<1+2);
ans=vector<vector<int>>(n+2,vector<int>(n+2));
res=xo=in=vector<int>(n<<1+2);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
cin>>ans[i][j];
if (ans[i][j]==-1)
{
in[i]++;
in[n+j]++;
e[i].push_back(n+j);
e[n+j].push_back(i);
}
else
{
xo[i]^=ans[i][j];
xo[n+j]^=ans[i][j];
}
}
}
for (int i=1;i<=n<<1;i++)
{
cin>>res[i];
}
for (int i=1;i<=n<<1;i++)
{
if (in[i]==1)
{
q.push(i);
}
}
while (!q.empty())
{
int now=q.front();
q.pop();
if(!in[now]) continue;//只要入队了，那么这一排已经排满了，那么我们需要把入度置为0，防止再一次入队
in[now]=0;
for (int i:e[now])//now这一排只有一个了（这一个值已经确定了），我们需要更新
{
if (in[i])
{
in[i]--;
change(now,i);//now的值确定会影响和now在一起的一排，也会有影响
if (in[i]==1)//但是只有入度为1的时候才可以确定i这一排只有一个的时候，才可以确定下来i那一排的唯一残缺位置的值，然后再影响和i在一起残缺的排
{
q.push(i);
}
}
}
}
for (int i=1;i<=n<<1;i++)
{
if (in[i])//只要入队列，那么一定会置位0(有残缺的)代表这一排已经补完整了，没有残缺的就是0,就是完整的。完整矩阵是每一排都是完整的，所以只要一个不完整，就不可以得到答案
{
cout<<-1<<'\n';
return ;
}
}
for (int i=1;i<=n;i++)//如果全部补完整，那么就输出
{
for (int j=1;j<=n;j++)
{
cout<<ans[i][j]<<" ";
}
cout<<'\n';
}
return ;
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
H
这一个呀，真是奇怪，一般我们每一条边的权值都是加起来的，但是这个是把这一条路的每一条边的权值组成一个数，第一条边是最高位（其他的依次在后面）
而这个题给了我们m条边，每一条边都会有一个权值（是双向的），但是u,v之间不一定只有一条边，
题目给了我们一条路径，我们需要得到这一条路上每一种路径值的期望（以为u,v之间的路不仅只有一条路）
而且这一个还需要取模，我们还需要用到快速幂
#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <map>
using namespace std;
#define int long long
#define mk(a,b) (a<<30|b)
const int mod=998244853;
int n,m,k;
int ksm(int x,int p)
{
int res=1;
while (p)
{
if (p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res;
}
int inv(int x)//如果用到取模，那么一定要用到逆元，否则可能会影响结果
{
return ksm(x,mod-2);
}
void solve()
{
map<int,vector<int>>h;//h记录每一条边的权值
cin>>n>>m>>k;
for (int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;//u,v一定不会超过2的30次方，那么u<<30|v一定不会撞上其他的两条边之间的权值
h[mk(u,v)].push_back(w);
h[mk(v,u)].push_back(w);
}
int now,nxt;//now是起点，nex是终点（这一个边）
cin>>now;//首先输出第一位
int ans=0;
int p10=ksm(10,k-2);//总共有k-1个数，第一个数是乘10的k-2次方，第二个数是乘10的k-1次方，这样一一求出每一位的值
const int ny10=inv(10);//上一个是10的x次方，和10的逆元相乘，p10就变成了10的x-1次方
for (int i=1;i<k;i++)
{
cin>>nxt;
int Now=mk(now,nxt);//这一条边
if (!h.count(Now))//如果不存在，那么一定不可以达到最后一个点，直接输出
{
cout<<"Stupid Msacywy!\n";
return ;
}//期望就是每一种值乘上概率的之和
int nynow=inv(h[Now].size());//这一步一共有多少种条路，如果有三条路，期望要除三，代表取这一个值的概率
for (int j:h[Now])//ans存的是从now到nxt的所有的可以的数(第1为取值是权值乘上10的k-2次方，是在最终的数中的一个部分)，p是此时在这一个位置应该乘的数，第一个是10的k-2次方这种，乘上这一个得到的数代表在这一条路里的值，还要乘上概率
{
ans=(ans+j*p10%mod*nynow%mod)%mod;
}
p10=p10*ny10%mod;
now=nxt;//更新边的两端
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
ios_base::sync_with_stdio(false);//这个一定要加，不然一定会超时
cin.tie(nullptr);
cout.tie(nullptr);
int t;
//cin>>t;
t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
K
这个我还推出了一个错误的公式（还是太菜）
这个是问你有n对括号需要配对，而且括号有k种，问我们总共有多少种可匹配的方式
我觉得我们可以先不要管括号有几种，算出有多少种括号的放置方式，然后按照排列组合的思想，每一对都有k种括号可以选择，那么我们需要的答案就是放置方式乘上k的n次方
不过这个后来才知道这个匹配问题的种类是卡特兰数
有这么几种都需要卡特兰数
1.进出栈问题
2.排队方式
3.二叉树生成问题
4.凸多边三角形划分
5.括号匹配问题
6.满二叉树个数
7.圆划分问题
8.填充问题
实现
int solve1() {
f1[0] = f1[1] = 1;
cin >> n;
for(int i = 2; i <= n; i++) {
for(int j = 0; j < i; j++) {
f1[i] += (f1[j] * f1[i-j-1]); //f(n)=f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(0)
}
}
printf("%lld\n",f1[n]);
return 0;
}
//公式2:
int solve2() {
f2[0] = f2[1] = 1;
cin >> n;
for(int i = 2; i <= n; i++)
{
f2[i] += f2[i - 1] * (4 * i - 2) / (i + 1); //f(n)=f(n-1)*(4*n-2)/(n+1)
}
printf("%lld\n", f2[n]);
return 0;
}
//公式3:
int solve3() {
cin >> n;
for(int i = 1; i <= 2 * n; i++) {
f[i][0] = f[i][i] = 1;
for(int j = 1; j < i; j++) {
f[i][j] = f[i - 1][j] + f[i - 1][j - 1]; //f(n)=c(2n,n)/(n+1)，利用组合数
}
}
完全代码在上面的一个博客
这些公式的推导证明点这儿
组合数点这儿
详细代码
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
const int maxn=1e5+10;
#define int long long
const int mod=1e9+7;
int t,n,k;
int f[maxn];
int ksm(int x,int p)
{
int res=1;
while (p)
{
if (p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res%mod;
}
int C(int a,int b)
{
int res=1;
for(int i=1,j=a;i<=b;i++,j--)
{
res=res*j%mod;
res=res*ksm(i,mod-2)%mod;//除以一个数转化为乘它的乘法逆元
}
return res;
}
int lucas(int a,int b)//求组合，如果需要取模，就会用到，前面博客可以详细了解
{
if(a<mod&&b<mod) return C(a,b);//a,b都小于p，定义求解
return C(a%mod,b%mod)*lucas(a/mod,b/mod)%mod;//代入卢卡斯公式
}
void solve()
{
cin>>n>>k;
int ans=C(n<<1,n)*ksm(n+1,mod-2)%mod*ksm(k,n)%mod;//用到第三个公式
cout<<ans<<'\n';
return ;
}
signed main ()
{
int t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}