已启用插件：KaTeX4Typecho
原文地址 ，评论已关闭，请在原文下评论。
rk800，终于上蓝啦
A.Optimal Currency Exchange
题意
卢布兑美元为 $a:1$ ，兑欧元为 $b:1$ 。美元面值最少为 $1$ ，欧元为 $5$ 。要把 $N$ 卢布尽量兑换出去，求最少剩下多少。
$N\le 10^8 \ , \ 30\le a,b\le 100$
题解
水题，枚举某种货币用了几张即可。我还sb的T了一次。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int n,a,b;
signed main()
{
n=read(); a=read(); b=read();
b*=5;
int ans=1e9;
int maxi=n/b;
for (int i=0;i<=maxi;i++)
{
int left=n-i*b;
int maxj=left/a;
ans=min(ans,left-a*maxj);
}
return !printf("%d",ans);
}B.Badges
题意杀我，看了5min才懂
题意
在 $B$ 个男孩和 $G$ 个女孩中有 $N$ 个人会参加活动，要给男孩准备蓝色徽章，女孩红色。共有 $N+1$ 组徽章，第 $i$ 组有 $i$ 个蓝色和 $N-i$ 个红色。要求不管来多少个男孩女孩都能准确分配徽章，问需要准备多少组。
$B,G\le 300$ 。
题解
就是求男孩人数种类和女孩人数种类的较大值。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int b,g,n;
signed main()
{
b=read(); g=read(); n=read();
int maxb=min(n,b),ming=n-maxb;
int maxg=min(n,g),minb=n-maxg;
return !printf("%d",max(maxb-minb,maxg-ming)+1);
}C.Bad Sequence
题意
给出一个括号序列，最多只能移动一个元素到另一个位置，问能否变成匹配的括号序列。
长度 $N\le 10^5$ 。
题解
$O(n)$ 扫一遍，如果有两个不匹配就直接输出 NO ，如果最后完美匹配就是 YES。因为不匹配的都是 )，所以如果有一个不匹配的且最后栈中有 $1$ 个元素也是 YES。其它情况是 NO 。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int n,cnt;
char ch[200005];
signed main()
{
n=read();
scanf("%s",ch+1);
bool flag=0;
for (int i=1;i<=n;i++)
{
if (ch[i]=='(') cnt++;
else if (ch[i]==')')
{
if (cnt) cnt--;
else if (!flag) flag=1;
else return 0&puts("NO");
}
}
if ((!flag && !cnt) || (flag && cnt==1)) return 0&puts("YES");
return 0&puts("NO");
}D.Treasure Island
upd:好像 1e9+7 和 1e9+9 都被卡掉了，看来出题人并不知道这个大质数。。所以以后还是应该多膜几个数。
题意
从 $(1,1)\rightarrow (n,m)$ ，只能向上向右走，图中的障碍物不能通过。问至少要再放置几个障碍物，使得无法到 $(n,m)$ 。
$n\times m\le 10^6$ 。
题解
可以发现答案最多为 $2$ ，即在 $(1,2)$ 和 $(2,1)$ 放上障碍物。所以只需要考虑答案为 $1,0$ 的情况。
如果答案为 $0$ ，说明本来就无法到 $(n,m)$ ，用 $\text{bfs}$ 搜索一遍即可判断。
如果答案为 $1$ ，就说明有一个格子是类似割点一样的状态。用 $gs[i][j]$ 表示从 $(1,1)\rightarrow (i,j)$ 的路径方案数，$gt[i][j]$ 表示从 $(n,m)\rightarrow (i,j)$ 的方案数，方程式为：
$$\begin{cases} gs[i][j]=gs[i-1][j]+gs[i][j-1] \\ gt[i][j]=gt[i+1][j]+gt[i][j+1] \end{cases}$$
如果存在一个点 $(i,j)$ ，使得 $gs[i][j]\times gt[i][j]=gs[n][m]$ ，就说明所有路径都会经过这个点，那么就可以放障碍物在这个点，答案为 $1$ 。
不过 $gs,gt$ 可能会很大，所以需要膜一个大质数。我当时想过多膜几个，但仔细想来就算要叉我构造数据也很麻烦，就没写。
其它情况答案就是 $2$ 。
#include<bits/stdc++.h>
#define ha 19260817
#define pii pair<int,int>
#define mp make_pair
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
char ch[1000005];
bool s[1000005],vis[1000005];
int n,m,gs[1000005],gt[1000005];
const int fx[2]={1,0},fy[2]={0,1};
inline int f(int x,int y) //将二维坐标转为一维
{
if (x<1 || x>n || y<1 || y>m) return 0;
return (x-1)*m+y;
}
inline void bfs()
{
vis[f(1,1)]=1;
queue <pii> q;
q.emplace(mp(1,1));
while (!q.empty())
{
int x=q.front().first,y=q.front().second; q.pop();
for (int i=0;i<2;i++)
{
int tx=x+fx[i],ty=y+fy[i];
if (tx<1 || tx>n || ty<1 || ty>m || s[f(tx,ty)] || vis[f(tx,ty)]) continue;
vis[f(tx,ty)]=1;
q.emplace(mp(tx,ty));
}
}
}
signed main()
{
n=read(); m=read();
for (int i=1;i<=n;i++)
{
scanf("%s",ch+1);
for (int j=1;j<=m;j++) s[f(i,j)]=ch[j]=='#';
}
bfs();
if (!vis[f(n,m)]) return 0&puts("0"); //如果无法到达说明答案是0
gs[f(1,1)]=1;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
if ((i!=1 || j!=1) && !s[f(i,j)]) gs[f(i,j)]=(gs[f(i-1,j)]+gs[f(i,j-1)])%ha;
gt[f(n,m)]=1;
for (int i=n;i;i--) for (int j=m;j;j--)
if ((i!=n || j!=m) && !s[f(i,j)]) gt[f(i,j)]=(gt[f(i+1,j)]+gt[f(i,j+1)])%ha;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
{
if ((i==1 && j==1) || (i==n && j==m)) continue;
if (1ll*gs[f(i,j)]*gt[f(i,j)]%ha==gs[f(n,m)]%ha) return 0&puts("1"); //(i,j)是割点，答案为1
}
return 0&puts("2");
}E.Petya and Construction Set
题意
要求构造一棵 $2N$ 个点树，使得 $i\rightarrow (i+1)$ 中间有 $d_i$ 条边。
$N\le 10^5$ 。
题解
神奇的构造题。
先按 $d_i$ 从大到小进行排序，然后把 $1,3,5,...,2N-1$ 这些奇数点按照排序后的顺序连成一条链。
然后把这些组依次扫一遍，同时用 deque 记录最长链，将偶数点与 距同组奇数点 $d_i$ 的点相连即可。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
struct node {
int id,d;
} s[100005];
int n;
deque <int> q;
signed main()
{
n=read();
for (int i=1;i<=n;i++) s[i].d=read(),s[i].id=i;
sort(s+1,s+n+1,[](const node &x,const node &y){ return x.d>y.d; });
for (int i=1;i<=n;i++)
{
q.emplace_back(s[i].id*2-1);
if (i<n) printf("%d %d\n",s[i].id*2-1,s[i+1].id*2-1);
}
for (int i=1;i<=n;i++)
{
printf("%d %d\n",s[i].id*2,q[s[i].d-1]);
if (s[i].d==(int)q.size()) q.emplace_back(s[i].id*2);
q.pop_front();
}
return 0;
}