A.Cards
题意
给 $n(n\le 10^5)$ 个字母，要求把它们组合成 one 或 zero 并输出为 1/0 。
题解
统计 n 和 z 的个数即可。
#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;
char s[100005];
signed main()
{
n=read();
scanf("%s",s+1);
int cntN=0,cntZ=0;
for (int i=1;i<=n;i++)
{
cntN+=s[i]=='n';
cntZ+=s[i]=='z';
}
for (int i=1;i<=cntN;i++) printf("1 ");
for (int i=1;i<=cntZ;i++) printf("0 ");
return 0;
}B.Multiplication Table
题意
给出一个 $n\times n(3\le n\le 1000)$ 的矩阵 $s$ ，$s_{ij}=a_i\times a_j$ 。现在把对角线上的数抹掉，求 $a$ 。
题解
第一行可以表示出 $a_2:a_3:a_4:...:a_n$ ，第二行可以表示 $a_1:a_3:a_4:...:a_n$ 。因为保证有解，所以对第三项求 $\mathrm{lcm}$ 后即可得到所有数的比值。
然后通过任意一个值就可以得到比值和实际的对应关系，然后就可以得到答案。注意先除后乘，防止越界。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll 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;
}
ll n,s[1005][1005];
ll gcd(ll x,ll y) { return y ? gcd(y,x%y) : x; }
signed main()
{
n=read();
for (ll i=1;i<=n;i++) for (ll j=1;j<=n;j++) s[i][j]=read();
ll lcm=s[1][3]*s[2][3]/gcd(s[1][3],s[2][3]);
ll d1=lcm/s[1][3];
for (ll j=2;j<=n;j++) s[1][j]*=d1;
s[1][1]=s[2][1]*(lcm/s[2][3]);
ll delta=sqrt(s[1][1]*(s[1][2]/s[2][1])); //对应关系
for (ll j=1;j<=n;j++) printf("%lld ",s[1][j]/delta);
return 0;
}C.Substring Game in the Lesson
题意
给出一个长度为 $n(n\le 5\times 10^5)$ 字符串，由 a 和 b 组成。Ann 和 Mike 玩游戏，Ann 先手。
初始状态为 $L=R=k$ ，用 $[L,R]$ 表示 字符串中 $S_L..S_R$ 的字典序，每次可以选择 $L'\le L \ , \ R'\geq R \ ([L',R'] < [L,R])$ ，并把 $L,R$ 挪到 $L',R'$ 。不能操作就算输。
问 $k=[1,n]$ 时谁能赢。
题解
可以发现只向右拓展字典序一定会增大，所以是没有意义的，只考虑向左移动。
向左移动只能移动到比 $S_L$ 小的，如果能移动肯定就直接移到最小的最左边的，后手输；否则先手直接输掉。
#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;
char s[500005];
signed main()
{
scanf("%s",s+1);
n=strlen(s+1);
int mn=1e9;
for (int i=1;i<=n;i++)
{
if (mn<s[i]) puts("Ann");
else puts("Mike"),mn=s[i];
}
return 0;
}D.Alex and Julian
内容转载自 https://www.cnblogs.com/Dup4/p/11552923.html#d.-alex-and-julian
题意
有一个集合 $B$，以及所有的整数组成的点，对于一个整数 $i$ ，那么该点的标号为 $i$，现在如果两个点 $(i,j)$ 满足 $|i-j|\in B$ ，那么 $(i,j)$ 之间有一条无向边。
问至少删去 $$ 中多少个数，使得所有点按要求连完边之后该图是一个二分图。
题解
没有奇圈的图是一个二分图
考虑 $x, y$ ，假设从 $1$ 出发，往后连边，那么他们相遇的点是 $lcm(x, y) + 1$ ，那么这个环的边数是：
$$\frac{lcm(x, y)}{x} + \frac{lcm(x, y)}{y} = \frac{x}{gcd(x, y)} + \frac{y}{gcd(x, y)}$$
我们发现要使得这个式子不能为奇数，那么显然有偶加偶或者奇+奇。
我们考虑先将两个数都尽可能除 $2$ ，直到这两个数的公约数中没有 $2$ 为止。
然后再来判断，那么现在至少有一个数是奇数，假设为 $x$ ，那么剩下的公约数肯定是个奇数。
那么考虑剩下的 $x, y$ ：
- 如果 $x, y$ 都是奇数，那么除掉一个奇数后还是奇数。
- 如果只有一个是奇数，那么偶数的那个除掉一个奇数还是偶数，奇数那个除掉奇数还是奇数，那么就是奇 + 偶 = 奇，不合法
所以所有可以共存的数必然满足他们的最低二进制位一样。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll 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;
}
ll n,s[200005];
bool vis[200005];
vector <int> v[64];
signed main()
{
n=read();
for (int i=1;i<=n;i++)
{
s[i]=read();
int j=0; for (;!(s[i]>>j&1);j++);
v[j].emplace_back(i);
}
ll mx=0,maxi;
for (int i=0;i<64;i++)
{
if ((ll)v[i].size()>mx)
{
mx=v[i].size();
maxi=i;
}
}
v[maxi].clear();
printf("%lld\n",n-mx);
for (int i=0;i<64;i++) for (auto j:v[i]) vis[j]=1;
for (int i=1;i<=n;i++) vis[i]&&printf("%lld ",s[i]);
return 0;
}E.Tourism
题意
有一个 $n(n\le 2\times 10^5)$ 点 $m(m\le 2\times 10^5)$ 边的无重边无自环的无向图，每个点有个点权。从 $1$ 出发，不能连续经过同一条边，问路径上点权和的最大值是多少。
题解
环上每一个点都可以遍历一遍，连接环之间的点也是；如果起点不在这些点上，那么这条边到环上的所有点也能被遍历，但起点到末梢的路径上则不能（到末梢再回来就会连续经过末端的边）。
剩下的与环相连的路径只能选择一条，可以拓扑排序DP，用 $f[i]$ 表示末梢到 $i$ 点权值和的最大值，所有环上的点中取 $f[i]$ 的最大值即是最优的路径。
答案即为所有没被拓扑的点的点权和 $+ \max(f[i])$ 。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll 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;
}
const ll N=200005;
struct Edge {
ll next,to;
} edge[N<<1];
queue <ll> q;
ll cnt,head[N],n,m,a,b,st,s[N],deg[N],f[N];
inline void add(ll u,ll v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
signed main()
{
n=read(); m=read();
for (ll i=1;i<=n;i++) s[i]=read();
for (ll i=1;i<=m;i++)
{
a=read(); b=read();
add(a,b); add(b,a);
deg[a]++; deg[b]++;
}
st=read();
if (n==1) return !printf("%lld",s[1]);
for (ll i=1;i<=n;i++)
{
if (i==st || deg[i]!=1) continue;
q.emplace(i);
}
while (!q.empty()) //拓扑排序
{
ll x=q.front(); q.pop();
deg[x]=0;
for (ll i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to;
if (!deg[y]) continue;
f[y]=max(f[y],f[x]+s[x]);
if (y==st) continue; //遇到起点则不继续
deg[y]--;
if (deg[y]==1) q.emplace(y);
}
}
ll ans=0,maxf=0;
for (ll i=1;i<=n;i++)
{
if (!deg[i]) continue;
ans+=s[i];
maxf=max(maxf,f[i]);
}
return !printf("%lld",ans+maxf);
}