zdw1999的博客比赛链接: https://acm.ayit.edu.cn/contest/11
题如其名, 直接取a*b输出即可
不知道为什么的请复习小学数学
标算代码: https://acm.ayit.edu.cn/submission/3459
所有数字不相同的情况构造成两段单调区间就能做出0~n-1的所有情况了
有相同数字的情况下, 按mx->mn,mx->mn...的方式反复选取可以得到最大混乱度
形式上类似3 2 1 3 2 1 3 2 1这样
然后我们扫描这个构造好的数列, 取混乱度达到m的位置i并对i~n排一次序即可
AYITOJ Round #4将于本周六晚上19:05开始辣
由于时间和牛客多校的题解直播冲突(之前没考虑到), 时间推迟到周日晚上
具体日期为2019-7-21 19:05~22:05, 时长3小时
题目总数为6题
出题人依旧是萌萌哒zdw1999(我)
如果想要参加请不要忘记在赛前戳一下报名
报名成功后, 红色的"报名"两个字会变成绿色的"已报名", 代表报名成功
如果赛前和赛中有任何疑问, 请站内私信管理员, 赛中使用提问功能或在QQ群650606345中提问
报名完成后那里会显示已报名, 否则应该是没有报名成功emmm, 可以再戳一下试试
请注意本OJ的赛制为OI+ACM混合赛制:
对OI选手: 代码提交后会立刻返回最终结果, 如果得分高于最后一次提交则会重新计算罚时, 比赛排名优先按分数其次按罚时
对ACM选手: 你可以选择只拿某道题一部分的分数(子任务)而不是一定过掉整道题, 排名优先按分数而不是解题数
Wish you high Rating ~
什么Java支持?当然是继续咕咕咕了,反正没人用(跑)
update: 本次的分数分布为 :
A{10}, B{15+25=40}, C{15+25+60=100}, D{100}, E{40+100+200}=340, F{100+200+300}=600.
比赛结束辣:
恭喜前5名选手
1.dogenya
2.cy1999
3.zdw1993
4.wudiii
设f[i]表示选择了第i行时能保留的最大行数
那么显然 f[i]=max(1,f[j]+1) , { $ j < i,第j行中每一列的数均大于第i行 $ }
直接按上式dp即可
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=1e9+7;
const int N=1e6+5;
ll A[505][505],f[505];
ll n,m;
bool isbig(int i1,int i2){
for(int i=1;i<=m;++i)
if(A[i1][i]<=A[i2][i])return 0;
return 1;
}
int main(){
std::ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;++i)A[0][i]=-(1LL<<60);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
cin>>A[i][j];
}
ll ans=1;
f[1]=1;
for(int i=2;i<=n;++i){
f[i]=1;
for(int j=1;j<i;++j)
if(isbig(j,i))f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
//cout<<f[i]<<endl;
}
cout<<n-ans;
return 0;
}我们从根开始做dfs, 并用一个树状数组$B$记录目前扫描过的所有点的权值的个数
每次走到一个点$i$, 我们先记录下$B.query(V_i-K,V_i+K)$的值
然后扫描这个点的所有子树, 扫描完毕后, 再次记录$B.query(V_i-K,V_i+K)$的值并减去之前的值
最后的值就是当前点的子树对当前点的贡献, 直接将其记录即可
最后将每个点的贡献全部加起来就是答案
特别地, 数值的范围是$10^9$, 所以我们需要先用一个map记录所有会用到的数并将其按顺序离散化处理
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=1e9+7;
const int N=3e5+5;
ll B[N*2];
void U(int i,ll x){++i;while(i<N*2)B[i]+=x,i+=i&-i;}
ll Q(int i){++i;ll r=0;while(i)r+=B[i],i-=i&-i;return r;}
ll A[N],L[N],R[N],fa[N],ans[N],n,K,a,l,r;
vector<int>G[N];
vector<int>WW;
map<int,int>Z;
void readll(ll &x){
char s=getchar();
while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}
ll dfs(int u){
ll res=0;
res-=Q(R[u])-Q(L[u]); //old sum
U(A[u],1);
for(auto &v:G[u]){
dfs(v);
res+=ans[v];
}
res+=Q(R[u])-Q(L[u]); //now sum
return ans[u]=res;
}
int main(){
readll(n);
readll(K);
for(int i=1;i<=n;++i){
readll(A[i]);
L[i]=A[i]-K;
R[i]=A[i]+K;
Z[L[i]]=Z[A[i]]=Z[R[i]]=1;
}
int cnt=0;
for(auto &i:Z)i.second=++cnt;
for(int i=1;i<=n;++i){
L[i]=Z[L[i]];
A[i]=Z[A[i]];
R[i]=Z[R[i]];
}
for(int i=2;i<=n;++i){
readll(fa[i]);
G[fa[i]].push_back(i);
}
dfs(1);
for(int i=1;i<=n;++i)
printf("%lld\n",ans[i]);
return 0;
}没啥好说的, 直接读取每个独立的字符串并特判其是否等于"henan", 是就替换即可
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=1e9+7;
const int N=1e6+5;
ll A[505][505];
ll n,m;
vector<int>V;
char s[1000];
int main(){
char c;
while(1){
while((c=getchar())==' ')putchar(' ');
if(~c&&c!='\r'&&c!='\n'){
s[0]=c;
scanf("%s",s+1);
if(string("henan")==s)printf("Henan");
else printf(s);
}else break;
}
return 0;
}直接找出出现次数最多的那个数即可
#include<bits/stdc++.h>
using namespace std;
int A[1025];
int main()
{
int n,x;
cin>>n;
while(n--){
cin>>x;
A[x]++;
}
x=0;
for(int i=1;i<=100;++i)
if(A[x]<A[i])x=i;
printf("%d\n",x);
}首先分析性质, 假设$a=7$, 那么$7/1=7, 14/2=7, 15/2=7.5, 21/3=7, 22/3=7.33, 23/3=7.66 $ ...
也就是说这是一个等差数列, 直到 $49/7=7$ 为止, 也就是$a^2$, 不难发现大于 $ a^2 $的数一定有解
所以我们把大于的部分特判掉直接计入答案, 然后加上一个等差数列再减去多加的部分即可
另外假设$F(a,l,r)$为答案的话, 显然$F(a,l,r) = F(a,0,r)-F(a,0,l-1)$, 这样可以忽略左端点, 少做一些特判
还有就是小心溢出(虽然我直接用了__int128过了就是了
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=1e9+7;
const int N=1e6+5;
ll n,a,l,r;
void readll(ll &x){
char s=getchar();
while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}
ll solve(ll a,ll r){
if(a>r)return 0;
ll ans=0;
if((__int128)a*a<=r){
ans+=r-a*a+1;
r=a*a;
}
if((__int128)a*a>r){
ll z=r/a;
ans+=z*(z+1)/2;
ll t=z*a+z-1;
if(t>r)ans-=t-r;
} else ans+=a*(a-1)/2;
return ans;
}
int main(){
//freopen("a.in","r",stdin);
readll(n);
while(n--){
readll(a);
readll(l);
readll(r);
ll ans=solve(a,r)-solve(a,l-1);
printf("%lld\n",ans);
}
return 0;
}从左向右扫描序列, 先忽略当前点 $A_i$ 对应的子树, 然后看下个点 $A_{i+1}$ 是否已经被忽略过
若没有, 直接暴力找 $LCA(A_i,A_{i+1})$ 在 $A_i$ 那侧的儿子 $P$, 然后忽略 $P$ 的整棵子树即可
而如果$A_{i+1}$之前被忽略过, 答案一定是不合法的
正确性证明:
复杂度证明
首先证明忽略子树的操作是均摊O(1)的
不难发现我们每次忽略某个点都一定会忽略整棵子树
所以我们遇到被忽略的点就可以直接跳过并忽略下一棵子树了
显然每个点最多只会做一次忽略, 所以复杂度是O(n+m), 因为是树所以总体复杂度是O(n)
然后证明LCA部分的复杂度是均摊O(1)的
暴力求LCA的复杂度其实就是求LCA时每个点会被"经过"次数的总和
求过LCA后, 上个点那侧的子树会被全部忽略, 所以显然经过次数不会再增加了(仅本次+1)
而另一侧的那个点, 在下一次求LCA后仍然是本侧的子树被忽略
但只有在LCA以下的那些点才会经过次数+1(且被忽略), LCA的祖先不会被忽略也不会被经过
到此时不难发现, 每个点最多只会被经过两次, 一次是作为"目标点"那边找LCA(不被忽略), 另一次是作为"出发点"那边找LCA(被忽略)
特别地, LCA本身可能会被"经过"多次, 但由于是单点, 且每次求LCA只会有一个LCA, 所以均摊后的复杂度仍然是O(1)
理论上, 倍增或ST之类的东西来预处理求LCA也是可行的, 但是由于巨大的常数和空间开销反而容易出现MLE和TLE
总结: 暴力出奇迹(划)
什么那LCA怎么求? 把深度暴力对齐然后不断暴力找父亲就好了
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=1e9+7;
const int N=1e6+5;
void readll(ll &x){
char s=getchar();
while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}
void readint(int &x){
char s=getchar();
while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}
struct node{node *t;int v;}E[N];
node *G[N];
int D[N],V[N],B[N],fa[N];
void dfs(int u,int d){
D[u]=d;
for(node *vv=G[u];vv;vv=vv->t)
dfs(vv->v,d+1);
}
void rush(int u){
for(node *vv=G[u];vv;vv=vv->t)
if(!V[vv->v])rush(vv->v);
V[u]=1;
}
int get(int x,int y){
while(D[x]<D[y])y=fa[y];
while(D[x]>D[y])x=fa[x];
while(fa[x]!=fa[y])x=fa[x],y=fa[y];
return x;
}
int main(){
ll T,n,m,ttt;
readll(T);
while(T--){
readll(n); readll(m);
for(int i=1;i<=n;++i)G[i]=0,V[i]=0;
for(int i=2;i<=n;++i){
readint(fa[i]);
E[i].t=G[fa[i]]; E[i].v=i;
G[fa[i]]=E+i;
}
dfs(1,0);
int ans=1;
for(int i=1;i<=m;++i)readint(B[i]);
for(int i=1;i<=m;++i){
if(!V[B[i]]){
rush(B[i]);
if(i>1){
int x=get(B[i-1],B[i]);
rush(x);
}
} else {
ans=0;
break;
}
}
puts(ans?"NOT BAD":"BAD GUGU");
}
}暴力枚举每一个状态然后用猜测串不断删掉不符合条件的状态即可, 想办法压压常剪剪枝就过了
sbzdw把输出的前导零吃了结果场上并没有过, 太菜了
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int ha=1e9+7;
const int N=1e6+5;
void readll(ll &x){
char s=getchar();
while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}
void readint(int &x){
char s=getchar();
while(~s&&s<'0'||s>'9')s=getchar(); x=s-'0';
while(~(s=getchar())&&s>='0'&&s<='9')x=x*10+s-'0';
}
struct node{
int v;
node *nxt;
node(){}
}*S,g[10000000]; int tot;
//int f[1000][1000],tot;
int now,n,m;
int V[10];
/*
int culc(int x,int y){
int cnt=0;
if(x%10==y%10)++cnt; x/=10; y/=10;
if(x%10==y%10)++cnt; x/=10; y/=10;
if(x%10==y%10)++cnt;
return cnt;
}
*/
void dfs(int i){
if(i==m){
//assert(now>=0);
// printf("%d\n",now);
g[tot].nxt=S;
g[tot].v=now;
S=g+tot++;
return;
}
for(int x=0;x<=9;++x){
if(!V[x]){
V[x]=1;
now=now*10+x;
dfs(i+1);
now/=10;
V[x]=0;
}
}
}
void init(){/*
for(int i=0;i<1000;++i){
for(int j=i;j<1000;++j)
f[i][j]=f[j][i]=culc(i,j);
}*/
readint(n);readint(m); S=0; now=0;
dfs(0);
g[tot].nxt=S;
S=g+tot++;
}
int judge(int x,int y){
int cnt1=0,cnt2=0;
int C1[10],C2[10];
for(int i=0;i<=9;++i)C1[i]=C2[i]=0;
for(int i=1;i<=m;++i){
if(x%10==y%10)++cnt1;
else ++C1[x%10],++C2[y%10];
x/=10; y/=10;
}
for(int i=0;i<=9;++i)cnt2+=min(C1[i],C2[i]);
return cnt1*100+cnt2;
}
int32_t main(){
init();
//int ww=0;
for(int i=1,md,y,x;i<=n;++i){
readint(md);readint(x);readint(y);
node *fa=S;
while(fa->nxt){
node *now=fa->nxt;
if(judge(now->v,md)!=x*100+y){
fa->nxt=now->nxt;//++ww;
continue;
}
fa=fa->nxt;
}
}
//cout<<ww<<" "<<tot<<endl;
printf(((string)"%0"+(char)('0'+m)+"d\n").c_str(),S->nxt->v);
}给出若干个非负数, 问最小的未出现的数
排个序直接扫描一下就好了
别问为啥wa3次，问就是我弱智
一开始没看到 "icebound的商店里一共有15件商品" 结果WA了一次
算出前15个商品的花费, 然后预处理dp, f[i][j]表示前i种商品组成j花费的方案数, 暴力转移即可
首先要知道nim博弈的结论: 直接按每堆数量取异或, 不为0则必胜
然后这题每堆石子是固定的, 所以预处理前缀异或和然后O(1)查询即可
树形dp. 首先随机选取一个根, 然后预处理出f[i]表示i的子树上所有点的权值和, g[i]表示i的整颗子树对当前i的贡献
转移 $ f[i]=w[i] + \sum_{j是i的儿子}\quad\ f[j] $ , $ g[i]=\sum_{j是i的儿子}\quad\ (g[j]+f[j]*dis(i,j)) $
其中 w[i] 表示i点的权值
然后从根再做一次dfs, 不断将父亲节点当做子节点的子树并将贡献向下传递给子节点即可
首先注意到判断两个矩阵是否能靠调整偏移量变成相等, 只需要判断其相邻元素的差值是否相等
然后对于这种区间比对, 不难想到用哈希来验证
为了压缩时间, 需要吧所有行的哈希再哈希一次, 然后比对矩阵的"所有行"和第一列是否相同即可
从高向低逐位扫描, 如果l,r都含这一位, 则加入答案, 否则将 $ 2^i - 1 $ 加入答案并跳出即可
另如果从当前位开始r后面所有位都是1, 那么显然将这些都直接加入答案并跳出即可
没看, 留坑(咕咕咕
把所有1的位置入队后直接做bfs即可
除了分块并没有想到更好的做法(咕咕咕
没看, 留坑(咕咕咕
裸的快速幂...
直接求和判正负
https://acm.ayit.edu.cn/contest/9
语言题, 注意三个数相加会爆int, 别的没了
标算代码: 2155
还是语言题, 每次读一个字符串并检查与上一个是否相等即可
标算代码: 2156
经典题, 用栈直接维护即可
对于一个左括号, 我们直接将其压入栈中
对于一个右括号, 我们直接查询栈顶的左括号是否与其匹配
是的话将其弹出, 否则显然序列已经不合法了
注意特判最后有剩余括号的情况
10分做法: 直接暴力模拟一步一步地走即可, 复杂度O(n^2)
30分做法: 考虑对10分做法的优化, 我们可以每次走一条边, 复杂度O(n)
80分做法1(假): 考虑到只有一组数据, 我们可以加一些魔法优化(ka chang), 然后复杂度变成O(n/x), 过了
80分做法2: 从外往里走好像很难看, 我们从里往外走试试
很容易就会发现轨迹总是一个矩形 + 一条线段
所以我们先求出终点位置, 然后求出(总步数-走的步数), 然后开个方求出轨迹的正方形部分边长, 然后特判掉线段部分就ok了
具体的话分类讨论可能麻烦一点, 复杂度O(1)
标算代码: 2158
80分做法3: 从外往里走当然也可以大致看做一个等差序列啦
所以我们直接二分环数然后微调位置也是可以的
不过zdw懒所以没有写
20分做法: 首先要发现传递是单向的, 所以我们贪心地把每个多余的数变成最近的缺少的数即可
于是直接模拟就能拿到20了
120分做法: 考虑维护, 可以用堆维护多余/缺少的数然后单向扫描即可
但实际上这里可以不用堆, 直接用两个指针来模拟即可
标算代码: 2159
十分经典的题目呢。。。解法非常多, 各种字符串处理工具都可以做
我这里用的是最菜最暴力的二分+哈希
二分公共前缀的长度然后直接比对哈希值就好了(捂脸)
标算代码: 2160
那么这场 Easy Round 各位玩的开心吗 )
欢迎在评论区留言吐槽或者讨论其他解法
AYITOJ Easy Round #1将于周一晚上19:05开始辣
具体日期为2019-3-18 19:05~21:35, 时长2.5小时
题目总数为6题, 前三名会发5,3,2元红包~
出题人依旧是萌萌哒zdw1999(我)
如果想要参加请不要忘记在赛前戳一下报名(如图所示)
如果赛前和赛中有任何疑问, 请站内私信管理员, 赛中使用提问功能或在QQ群650606345中提问
报名完成后那里会显示已报名, 否则应该是没有报名成功emmm, 可以再戳一下试试
请注意本OJ的赛制为OI+ACM混合赛制:
对OI选手: 代码提交后会立刻返回最终结果, 如果得分高于最后一次提交则会重新计算罚时, 比赛排名优先按分数其次按罚时
对ACM选手: 你可以选择只拿某道题一部分的分数(子任务)而不是一定过掉整道题, 排名优先按分数而不是解题数
Wish you high Rating ~
题目的分数分布为: 5, 10, 40, 80, 120, 200
Java当然是继续咕咕咕了
现在已经支持查看自己的程序运行的详细情况了(点提交记录查看详情即可)
比赛结束辣:
恭喜前5名选手
1.aoaoao
3.cy1999
4.zdw1993
https://codeforces.com/contest/1099
直接按照题意模拟即可: 47974196
这题要注意的是不一定真的要正好凑够n个, 而是可以少凑成n+x个的矩阵然后少绘制x个
弱智的zdw读错了题然后WA了一波
代码: 47981321
裸的贪心题, 长度过多就删除, 长度过少就增加, 不足就是无解
注意 * 标记的字符是可以有0~任意个, 也就是可以删除的
代码: 47987204
由于题目给的是从当前点到根的和, 所以我们可以把两个节点上的前缀和尽可能放在他们的公共祖先上
我们可以在每个点上先补足前缀缺失的值, 然后贪心地将每个点的值向根移动
当一个点有多个儿子时, 取所有儿子中最小的那个作为该节点的值即可
代码: 48001022
留坑, 回头补
不难发现吃饼干和走路是互相独立的, 而且经过的点确定之后, 一定是先吃花费少的饼干更优
所以我们做dfs并用树状数组维护当前经过的路径上的饼干按"每块花费" 的 花费 和 数量 的前缀和
然后减去路途的花费后, 用剩下的时间在树状数组上二分出能吃到的饼干的最多数量即可
这题 $n$ 只有 $10^5$ 且单儿子的点会被直接切断, 所以 $O(nlog^2n)$ 跑的也很快
代码: 48014890
影响每个人排名的有 罚时 和 分数 两个值
当你在一道题上得到分数时, 这题会增加你的罚时, 增加的量为:
你最早的最高分数提交记录的提交时间 + 这次提交之前的非CE提交数 * 1200(秒)
分数的话当然是取每道题上获取的历史最高分的总和.
排名时优先按照分数, 分数高的在前面, 分数相等的情况下, 罚时低的在前面
另外显而易见的就是, 如果某题没有部分分, 那么对这题来说就是完全的ACM赛制
如果仍然有任何疑问请直接在评论区提问即可, 我看到后会尽快回答
比赛链接: https://acm.ayit.edu.cn/contest/6
后四题没有一个被AC的还是有点意外的...
感觉大家都在忙着收部分分2333
嗯，不扯了，我们进入正题:
简单的签到题, 直接判断即可
标算代码: https://acm.ayit.edu.cn/submission/1000
由于数字和运算符之间有空格, 所以直接读取后进行相应计算即可
其实是出题人自己懒了
PS: 出这题的时候愚蠢的zdw把幂运算设的太小了结果不用快速幂也能过
AYITOJ Round #3将于本周日下午14:05开始辣
具体日期为2018-12-16 14:05~18:05, 时长4小时
题目总数为6题(目前未定), 前三名会发5,3,2元红包~
出题人依旧是萌萌哒zdw1999(我),
另外感谢 cy1999 帮助验题~
如果想要参加请不要忘记在赛前戳一下报名
如果赛前和赛中有任何疑问, 请站内私信管理员, 赛中使用提问功能或在QQ群650606345中提问
报名完成后那里会显示已报名, 否则应该是没有报名成功emmm, 可以再戳一下试试
请注意本OJ的赛制为OI+ACM混合赛制:
对OI选手: 代码提交后会立刻返回最终结果, 如果得分高于最后一次提交则会重新计算罚时, 比赛排名优先按分数其次按罚时
对ACM选手: 你可以选择只拿某道题一部分的分数(子任务)而不是一定过掉整道题, 排名优先按分数而不是解题数
Wish you high Rating ~
什么Java支持?当然是继续咕咕咕了,反正没人用(跑)
update: 题目的分数分布为: 20, 70, 240, 300, 400, 600
Server time: 2024-09-22 01:39:46