|
NOIp2017 时间复杂度 题解分析模拟，模拟，还是模拟。 给定了 $n$ 行 A++ 代码和一个小明算的时间复杂度，判断此复杂度是否正确（$Yes$ 和 $No$）。 若代码存在语法问题（$F$ 与 $E$ 未匹配或变量名重复定义），则输出 $ERR$。 思路循环可以嵌套，也可以并列，考虑用栈来模拟每一组循环。 使用两个栈，一个使用结构体维护循环信息 $st$，一个维护当前的时间复杂度信息 $opts$。 为了方便，开始之前先将 $opts$ 内压入一个 0。 （本题解时间复杂度表示中，$w$ 表示复杂度为 $O(n^w)$。）
接下来是模拟流程。 维护一个整数数组 $u$，$u_c$ 表示字符 $c$ 在此时被使用的次数。 如果读取到 $F$： - 将循环的参数 $i$、$x$ 和 $y$ 压入 $st$；为方便，将 $n$ 看做 101。 - 如果此前参数 $i$ 已经被使用，则将 $isERR$ 设为 1； - 将 $u_i$ 的值增加 1； - 将 0 压入 $opts$。
如果读取到 `E`： - 若此时栈空，即没有循环需要退出，$isERR$ 设为1； - 否则弹出当前 $st$ 顶的循环，使用 $opts$ 栈顶更新 $opts$ 次顶的时间复杂度。弹出栈顶。将 $u_i$ 的值减少 1。
当 $l$ 行代码运行完毕，若 $st$ 栈内仍有元素，则将 $isERR$ 设为 1。 最后，判定算得结果是否与小明的答案相同即可。 更新时间复杂度本题解将着重讲解一下时间复杂度的更新。 对于一层循环 ${i,x,y}$，其复杂度与内部的所有嵌套的子循环有关，且为所有嵌套的子循环中时间复杂度的最大值，再加上该循环自身的复杂度。 首先，若此循环中 $x>y$，即无法进入，则此循环及往下的复杂度一定为 $O(1)$，表示为 0； 若 $y=101$ 且 $x\neq 101$，则此循环的复杂度为 $O(n)$，表示为 1。 特别地，$x$ 与 $y$ 都为 101 时，此循环的复杂度仍记为 $O(1)$。 CODE
#include<bits/stdc++.h>
#define ll long long
#define rev(x) reverse(x.begin(),x.end())
#define lb(x) (x&(-x))
using namespace std;
struct node{
char varName;
int from,to;
node(){
varName=' ';
from=to=0;
}
bool ableToRun(){
return from<=to;
}
};
int varNameIsUsed[26];
stack<node> st;
stack<int> opts;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
// freopen("2017complexity.in","r",stdin);
// freopen("2017complexity.out","w",stdout);
int t;cin>>t;
while(t--){
while(!st.empty()) st.pop();
while(!opts.empty()) opts.pop();
opts.push(0);
memset(varNameIsUsed,0,sizeof varNameIsUsed);
bool isERR=false;
int ls;cin>>ls;
string ops;cin>>ops;
for(int lne=1;lne<=ls;lne++){
char p;cin>>p;
if(p=='F'){
node wp;
cin>>wp.varName;
string fm,tm;cin>>fm>>tm;
if(fm=="n") wp.from=101;
else{
int nw=0;
for(int i=0;i<fm.length();i++) nw=nw*10+fm[i]-'0';
wp.from=nw;
}
if(tm=="n") wp.to=101;
else{
int nw=0;
for(int i=0;i<tm.length();i++) nw=nw*10+tm[i]-'0';
wp.to=nw;
}
if(varNameIsUsed[wp.varName-'a']) isERR=true;
varNameIsUsed[wp.varName-'a']++;
st.push(wp);
opts.push(0);
}else{
if(!st.empty()){
node tp=st.top();
st.pop();
varNameIsUsed[tp.varName-'a']--;
int nwOpt=(opts.top()+(tp.to==101&&tp.from!=101?1:0))*tp.ableToRun();
opts.pop();
int kkk=opts.top();
opts.pop();
kkk=max(kkk,nwOpt);
opts.push(kkk);
}else{
isERR=true;
}
}
}
if(!st.empty()) isERR=true;
int opsINT=0;
if(ops=="O(1)") opsINT=0;
else{
for(int i=4;i<ops.length()-1;i++) opsINT=opsINT*10+ops[i]-'0';
}
if(isERR) cout<<"ERR"<<endl;
else if(opsINT==opts.top()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
题目2865 [NOIP 2017]时间复杂度
 1
评论
2024-11-09 02:58:47
|
|
|
题目3055 [NOIP 2018]赛道修建
4
评论
2024-10-24 23:23:50
|
|
|
                
题目4031 [USACO24 Open Bronze]Farmer John’s Favorite Permutation
2
评论
2024-10-24 12:32:02
|
|
|
CSP 2022J 解密 题解首先分析题目对于给定的 $n$，$e$，$d$，询问是否存在一组正整数 $p$，$q$ 满足 $pq=n$ 且 $(p-1)(q-1)+1=ed$。 S.1考虑暴力。 枚举每组 $pq=n$，检查是否满足 $(p-1)(q-1)+1=ed$。 时间复杂度 $O(k\sqrt{n})$，预计20pts（但实际上40pts）。 S.2（正解）注意到 $n$ 的范围特别大，考虑分析题目的式子。 $$(p-1)(q-1)+1=ed$$ $$pq-p-q+2=ed$$ $$n-p-q+2=ed$$ $$n-ed+2=p+q$$ 令 $m=n-ed+2$。 结合上面的 $pq=n$，注意到这是一个方程。 尝试换元，得到一元二次方程 $p^2-mp+n=0$，只需检验两个根是否都为正整数即可。 时间复杂度 $O(k)$。预计100pts。
题目3778 [CSP 2022J]解密
4
评论
2024-10-09 20:46:13
|
|
|
这道题可以使用分治算法和暴力枚举来解决先写一下分治的思路我们需要找到一个k使得k%n的值在L和R区间内最大。
递归步骤：
要先知道： 如果 L > R，说明区间为空，返回 0。 步骤： 计算中间值 mid。 如果 mid % n 不为 0，则比较 mid % n 和右半边 [mid + 1, R] 的结果，返回较大的值。 如果 mid % n 为 0，则递归地在左半边区间 [L, mid - 1] 查找。 举个栗子
假设 L = 3, R = 10, n = 5 第一次调用 find(3, 10, 5)： mid = 6 mid % n = 6 % 5 = 1（非零） 比较 1 和 find(7, 10, 5) 的结果。 第二次调用 find7, 10, 5)： mid = 8 mid % n = 8 % 5 = 3（非零） 比较 3 和 find(9, 10, 5) 的结果。 第三次调用 find(9, 10, 5)： mid = 9 mid % n = 9 % 5 = 4（非零） 返回 4。 第二次调用返回 3 和 4 比较，返回 4。 第一次调用返回 1 和 4 比较，返回 4。 最终答案为 4。 OK，写个栗子（第一次发题解，用ai再给我改了一遍）
// 计算按照规则分糖果后剩余的数量 int jisuan(int n, int k) { int shengYu = k; while (shengYu >= n) { shengYu -= n; } return shengYu; } // 分治算法函数 int fenZhiSuanFa(int n, int zuoBian, int youBian) { if (zuoBian == youBian) { return jisuan(n, zuoBian); } int zhongJian = (zuoBian + youBian)/2; int shengYu_zhongJian = jisuan(n, zhongJian); int shengYu_zhongJian_jia_1 = jisuan(n, zhongJian + 1); int shengYu_zhongJian_jian_1 = jisuan(n, zhongJian - 1); if (shengYu_zhongJian >= shengYu_zhongJian_jian_1 && shengYu_zhongJian >= shengYu_zhongJian_jia_1) { return shengYu_zhongJian; } else if (shengYu_zhongJian_jian_1 > shengYu_zhongJian) { return fenZhiSuanFa(n, zuoBian, zhongJian - 1); } else { return fenZhiSuanFa(n, zhongJian + 1, youBian); } }
|
|
|
分糖果这道题也是肥肠简单的： 只要找到了规律就可以迎刃而解了 再看题解之前可以先想想自己是怎么写的： [1]模拟分糖果的过程？ [2]找规律？ 聪明的你一定第一次就想到了要找规律 （第一次用的模拟 事实证明会爆）！！！ 那么该怎么做呢？ 在分糖果这道题中存在一个下限和上限 也就是L和R 动用那你聪明的小脑瓜就可以发现 如果（if） L/n等于R/n 当这种情况存在的时候 我们的结果就是r%n tip:也就是上限(R)模人数(n) 显而易见的 另外的（else） 也就是说当R/n不等于L/n的时候 我们怎么办呢？ 这时候就可以再思考一下下了捏 当这种情况是 也就说明了再上线R和下线L中间一定存在一种剩余糖果最多的情况 所以这种情况的结果就是n-1 tip:也就是人数(n)减去一 显而易见的 那么这道题是不是就迎刃而解了呢！ 是的！ 代码附上 希望能帮到OIer们 点个赞呗！！！
题目3615 [CSP 2021J]分糖果
AAAAAAAAAA
7
14 条 评论
2024-10-03 21:40:06
|