A 汪汪汪汪汪？
1 20 樱trick 高山春香 园田优
2 35 总之就是非常可爱 由崎司 由崎星空
3 4 双星物语2 拉格那·瓦伦汀 爱尔温·德·穆普利亚
5 6 竭泽 滑稽 （太甜了太甜了！）
7 38 辉夜大小姐想让我告白 白银御行 四宫辉夜
8 18 徒然喜欢你 皆川由纪 古屋纯
9 36 俺物语 大和凛子 刚田猛男
10 40 徒然喜欢你 高濑春彦 神田沙希
11 15 堀与宫村 堀京子 宫村伊澄
12 17 冰上的尤里 胜生勇利 维克托·尼基福罗夫
13 37 Citrus 蓝原芽衣 蓝原柚子
14 29 青春猪头少年不会梦到青春兔女郎学姐 樱岛麻衣 梓川咲太
16 19 理科生坠入情网，故尝试证明。 雪村心夜 冰室菖蒲
21 27 安达与岛村 岛村抱月 安达樱
22 24 龙王的工作！空银子 九头龙八一
23 32 阿宅的恋爱 二藤宏嵩 桃濑成海
25 33 高木同学 高木 西片
26 34 龙与虎 逢坂大河 高须龙儿
28 30 樱花庄 椎名真白 神田空太
31 39 纯情罗曼史 宇佐见秋彦 高桥美咲
B 发糖啦!!
这个题思路其实很好理解，将一个数转化为x进制后，只有一个数不为0，所以我们只需要保证这一点，暴力的方法便出来了
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
void solve(){
ll n,res=0,len=0;
cin>>n;
for(int i=2;i<=n;i++){
int s[40],x=0,t=n;
while(t) s[x++]=t%i,t/=i;
int flag=1;
for(int i=0;i<x-1;i++) if(s[i]!=0) flag=0;
if(flag&&x>len) len=x,res=i;
}
cout<<res<<"\n";
}
int main(){
ll T;
cin>>T;
while(T--)
solve();
} 然后我们在仔细一发现，其实我们就对于n来说大于n的数都只能保证长度为1，而n可以至少保证长度为2，所以大于n的不用考虑，其次我们发现如果要使个位数为0一定是n的约数才行，所以我们要查询n的约数，对于每个约数去寻找最大长度。
（还是不够毒瘤，想着不要下手太狠，结果还是被巨巨们卡过去了，早知道在毒瘤一点了）
最开始在测的时候std是200ms，怕你们常数大就没卡常
#include<iostream>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
int su[N];
bool vis[N];
ll read(){
ll x=0;char ch;
for(ch=getchar();!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x;
}
void ptr(ll n){
cout<<n<<"\n";
}
void oula(){
for(ll i=2;i<N;i++){
if(!vis[i])su[++su[0]]=i;
for(int j=1;j<=su[0]&&su[j]*i<N;j++){
vis[i*su[j]]=true;
if(i%su[0]==0)break;
}
}
}
pair<int,int> s[40];
int len,c[N],ans=0;
void dfs(int i,ll res){
if(i==len)
c[ans++]=res;
else {
ll t=1;
for(int j=0;j<=s[i].second;j++)
dfs(i+1,res*t),t*=s[i].first;
}
}
void fe(ll n){
len=0,ans=0;
for(int i=1;i<=su[0]&&su[i]<=n/su[i];i++)
if(n%su[i]==0){
int x=0;
while(n%su[i]==0)n/=su[i],x++;
s[len++]={su[i],x};
}
if(n!=1)s[len++]={n,1};
dfs(0,1);
}
void solve(){
ll n=read(),res=0,tt=0;
fe(n);
for(int i=1;i<ans;i++){
ll x=0,t=n;
while(t){
if(t%c[i]!=0&&t>c[i])break;
x++;
t/=c[i];
}
if(!t)
if(x>tt)tt=x,res=c[i];
else if(res>c[i])res=c[i];
}
ptr(res);
}
int main(){
oula();
int T=read();
while(T--)
solve();
}C 真假对象
首先这个题第一个诈骗点就是，牛客的题目前还没有自动连接跳转这个功能，所以等待10秒的同学踩到了第一个坑。
这个时候我们就需要去寻找题目真正的玩法，有打过去年愚人节比赛的同学应该能知道超链接。
其次，题目的名称叫做真假对象，也就是有真真假假个对象，答案也有真真假假的答案，这里为了良心一点，我只放了一个假答案，所以最多wa一发
那么真的要去试嘛？
我将答案放在真那个字上面，代表真答案。
其他的答案我们可以发现，跳转页面的标题是“恭喜你找到了正确答案（”
这个梗的由来是来自于，水军帮忙洗地，括号内应该是（5毛钱一条，括号删干净）也就是说说的不是真话。
而我留了一个括号就是说明这句话是假的。
ps.为了误导大家，真不愧我在群里没事加了那么多次括号。
D 亲密数
先通过筛法求出 1~n 每个数的因子之和，复杂度 。
之后按题意进行模拟即可。
参考代码：
#include<bits/stdc++.h>
using namespace std;
int dp[100010];
int f(int x){
int i;
int sum=1;
for(i=2;i*i<x;i++){
if(x%i==0)sum+=i+x/i;
}
return sum+(i*i==x)*i;
}
int in(int l,int r,int x){
return x>=l&&x<=r;
}
int main(){
int n=1e5,i,j,k;
for(i=1;i<=n;i++){
dp[i]=f(i);
}
int l,r;
cin>>l>>r;
for(i=l;i<=r;i++){
int j=dp[i];
if(in(l,r,j)&&j!=i&&dp[j]==i){
cout<<j<<" "<<i<<endl;
return 0;
}
}
cout << -1 << endl;
} E 推理游戏
不难猜出，死者是在玻璃上留下了凶手信息。但是玻璃上什么都没有，这是为什么呢?
我们考虑到阅览室先关闭了空调，之后一段时间内，阅览室温度升高，而隔壁空调仍然是开启状态，因此温度差使得阅览室侧玻璃上起了水雾，这样死者就在玻璃水雾上写下了关于凶手的信息(大家想一想冬天在玻璃上写字的情况)。之后，隔壁的空调也被关闭，温度差消失，玻璃上的水雾也会消失，因而就造成了玻璃上啥都没有的情况。
那么根据以上这点，死者死于温度差存在的期间，就肯定是阅览室内的人杀害了死者。如果是阅览室隔壁的人杀害死者，那么杀人之后还回到隔壁继续拍摄，并关闭空调，就很没必要。可能有人会说，是隔壁的杀人后发现了死者留下的信息，回隔壁关空调了。可是如果真发现了，明显用手把水雾抹干净较为方便，回去关空调稍显麻烦了。
那么凶手确定，凶器就不难猜出是阅览室的书籍了。将若干书本堆起来(或者直接使用现代汉语词典那种级别)，用书本的边缘棱角部分敲击死者后脑，从而造成死者失血死亡。
本题目是游戏《诡计x逻辑》的练习关卡精简改编而成，正式关卡的篇章更难也更有趣，对推理有兴趣的同学可以去玩一玩。
F 清楚姐姐的翅膀们
看到匹配可能会往二分图匹配上面去想，但是本题是一道经典的一般图匹配。
建模如上图，和朴素的二分图匹配一样，也是双层网络模型，不同的地方在于下层表示妹子的网络要“拆点”。
比如说现在只有 1 个妹子，然后有 3 个物品，这个妹子喜欢这三个物品。
嗯，上边表示物品，下边表示妹子，注意这里需要拆点，一个妹子拆成两个点，并且需要
连一条“自我匹配边”，当“自我匹配边”生效时，意味着她将放弃选取蝴蝶结。
然后跑最大匹配。
对于每个妹子而言，仅有三种匹配情况：
1、选取两件蝴蝶结
此时上边的集合有两个点参与匹配，这表示这两件蝴蝶结被这个妹子选走了，然后她很开
心。同时，这个妹子贡献的最大匹配数+2
2、选一件蝴蝶结
此时上面的集合只有一个点参与匹配，这表示这妹子妹子拿了一件蝴蝶结，这个妹子是不开心
的。同时，这个妹子贡献的最大匹配数+1
3、不拿蝴蝶结
自我匹配，不会选取任何一个蝴蝶结集合中的蝴蝶结，这个妹子不开心，同时，这个妹子贡献的最大匹配数+1。
那你就发现了，无论怎样，每个妹子贡献的最大匹配数都会+1，并且当且仅当这个妹子开
心的时候，最大匹配数+2。
So，答案=最大匹配数-n。
std https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48558065
G ORMAX
1. 对于查询操作来说，或起来的数越多越好，所以该操作为查询区间或的值。
2. 修改操作为线段树常规操作，对该区间打上 Lazy 标记即可。下一次对该区间修改是覆盖上个区间的 Lazy 就行。
查询和修改操作均为 O(logn) 总时间复杂度为 O(mlogn)
#include<bits/stdc++.h>
#define ll long long
#define MAX_B 20
using namespace std;
const int N=1000005;
#define ls k<<1
#define rs k<<1|1
inline int read(){
int x=0;char ch;
for(ch=getchar();!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x;
}
struct node {
int l,r,lzy;
int sum;
}tr[N<<2];
int a[N],n,m;
void pushup(int k) {
tr[k].sum=tr[ls].sum|tr[rs].sum;
}
void build(int k,int l,int r) {
tr[k].l=l,tr[k].r=r,tr[k].lzy=0;
if(l==r) {
tr[k].sum=a[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(k);
}
void pushdown(int k) {
if(tr[k].lzy==0) return;
int x=tr[k].lzy;
tr[ls].lzy=tr[rs].lzy=tr[ls].sum=tr[rs].sum=x;
tr[k].lzy=0;
}
int query(int k,int l,int r) {
if(tr[k].l>=l&&tr[k].r<=r) {
return tr[k].sum;
}
int mid=(tr[k].l+tr[k].r)>>1;
pushdown(k);int res=0;
if(l<=mid) res|=query(ls,l,r);
if(r>mid) res|=query(rs,l,r);
return res;
}
void update(int k,int l,int r,int lzy) {
if(tr[k].l>=l && tr[k].r<=r) {
tr[k].sum=lzy;
tr[k].lzy=lzy;
return;
}
pushdown(k);
int mid=(tr[k].l+tr[k].r)>>1;
if(l<=mid) update(ls,l,r,lzy);
if(r>mid) update(rs,l,r,lzy);
pushup(k);
}
int main() {
//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
build(1,1,n);
while(m--) {
int op;
scanf("%d",&op);
if(op==2) {
int l,r,x;
l=read(),r=read(),x=read();
//cin>>l>>r>>x;
//scanf("%d%d%d",&l,&r,&x);
update(1,l,r,x);
}
else {
int l,r;
l=read(),r=read();
//scanf("%d%d",&l,&r);
int ans=query(1,l,r);
printf("%d\n",ans);
}
}
return 0;
} H 牛妹的七夕闯关
按照题意模拟即可，考到到达 asum ，令 x=sum%(a+b) 若 x<a 则无法通过，需等待 a-x 单位时间才可通过。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
struct db {
ll p,a,b;
}c[N];
bool cmp(db x,db y) {
return x.p<y.p;
}
int main() {
ll n;
int m;
cin>>n>>m;
for(int i=1;i<=m;i++) {
cin>>c[i].p>>c[i].a>>c[i].b;
}
sort(c+1,c+1+m,cmp);
ll now=0;
c[++m].p=n,c[m].a=0,c[m].b=1;
for(int i=1;i<=m;i++) {
now+=c[i].p-c[i-1].p;
ll res=now%(c[i].a+c[i].b);
if(res<c[i].a) {
now+=c[i].a-res;
}
//cout<<now<<endl;
}
cout<<now<<endl;
return 0;
} I 永远在一起
很容易想到 dp。
先不考虑「恋串」长度的奇偶性。
设 dp[i][W/F] 表示第 i 个字符为 W/F，以第 i 个字符结尾的最长的「恋串」的长度。
很容易想到转移方程：
- s[i]=W，dp[i][W]=dp[i-1][F]+1
- s[i]=F，dp[i][F]=dp[i-1][W]+1
- s[i]=?，dp[i][W]=dp[i-1][F]+1，dp[i][F]=dp[i-1][W]+1
扫一遍 |s|，累加上 floor(max(dp[i][W], dp[i][F])/2)，这样就能保证「恋串」的长度为偶数。
顺便提一下，长度为 k 的一个「恋串」p 中，以 p[k] 结尾的「恋串」数量为 floor(k/2)，由于我们在之前不考虑「恋串」长度的奇偶性，所以要向下取整。
例如 WFWFWF 中，就有 WF，WFWF，WFWFWF 共 3 个「恋串」。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define N 200010
using namespace std;
char s[N];
ll dp[N][2];
void Sol(){
scanf("%s", s);
int n = strlen(s);
for(int i = 0 ; i < n ; i++){
if(s[i] == '?') continue;
s[i] = (s[i] == 'W') ? '0' : '1';
}
ll ans = 0;
memset(dp, 0, sizeof(dp));
if(s[0] == '?') dp[0][0] = dp[0][1] = 1;
else dp[0][s[0] - '0'] = 1;
for(int i = 1 ; i < n ; i++){
if(s[i] == '1') dp[i][1] = dp[i - 1][0] + 1;
else if(s[i] == '0') dp[i][0] = dp[i - 1][1] + 1;
else dp[i][1] = dp[i - 1][0] + 1, dp[i][0] = dp[i - 1][1] + 1;
}
for(int i = 0 ; i < n ; i++)
ans += (max(dp[i][0], dp[i][1]) / 2);
printf("%lld\n", ans);
}
int main(){
Sol();
return 0;
} 本场比赛出题团共有7位出题人,希望大家玩的开心~
出题人1：
出题人2：
出题人3：
出题人4：
出题人5：
出题人6：
出题人7：
全部评论
(8) 回帖