题目链接: https://ac.nowcoder.com/acm/contest/68444#question
已通过:B C E K
C题+K题–手搓规律
https://ac.nowcoder.com/acm/contest/68444/C
https://ac.nowcoder.com/acm/contest/68444/K
C题:
长记性:没写错的情况下,用循环超时就说明方法不对,直接从本质入手,大量举例,去找最基本的规律
#include<iostream>
#define int long long
using namespace std;
signed main(){
int n,cnt=0;
cin>>n;
if(n%3==0)cout<<(n-3)/3;
if(n%3==1)cout<<(n-1)/3*2;
if(n%3==2)cout<<(n-2)/3*2;
return 0;
}
历程:一开始写完整循环-超时>>发现组成的两数顺序一正一反正好两遍可以只循环一半-还是超时>>只能换个思路展开各种例子分析,找到模3的余数不同对应的不同规律-AC
回过头来想循环相当于把问题又抛回给编译器,没有任何思考含量,肯定是找规律
赛后反思-完全类似Educational Codeforces Round 156 (Rated for Div. 2) A
https://codeforces.com/contest/1886/problem/A
当时补的题: https://www.acwing.com/file_system/file/content/whole/index/content/10200094/
这种题的共性:一开始几个不一定符合总体规律,但总体需要满足一些要求(从题面);可以将情况按一定标准分为几类(比如取模后余数的情况,总归也就那几种)
K题:
看见回文虽然吃过一次亏,但还是在想能不能用类似双指针这种来解决,穷尽所学发现不对劲,然后因为刚补完cf字符串回文的问题,感觉不应该是正经判断回文,所以分析一下回文的情况:aa,bb,cc,a _ a,b _ b,c _ c,一共两类六种情况,再多举例也是这样,所以直接遍历一遍特判这两类情况,使其他的均为不能回文
void solve(){
string s;
cin>>s;
int cnt=-1;
int len=s.length();
for(int i=0;i<len;i++)
{
if(s[i]==s[i+1]) cnt=2;
else if(s[i]==s[i+2]) cnt=3;
}
cout<<cnt;
}
E题-递归:
https://ac.nowcoder.com/acm/contest/68444/E
这个题真的不看其他人的代码都不知道自己什么水平……
我的:
#include<iostream>
#define int long long
using namespace std;
int ans=0;
void dfs(int cnt){
for(int i=1;i<=cnt;i++)ans++;
}
signed main(){
int t;
cin>>t;
int cnt=1;
while(t--)
{
dfs(cnt);
cnt+=2;
}
cout<<ans;
return 0;
}
是真的想让函数运行出结果,在键盘读入的n层循环中调用函数,实现ans的++操作,然后让cnt+2,实现cnt从1开始的递增操作。
佬:
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int n; cin >> n;
cout << n * n << endl;
}
观察直接找出规律
B题-环形公路:
https://ac.nowcoder.com/acm/contest/68444/B
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N1=1e5+10;
signed main(){
int n;
int a[N1];
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];}
int x,y;
cin>>x>>y;
if(x>y) swap(x,y);
int shun=0,ni=0;
for(int i=x;i<y;i++) shun+=a[i];
ni=sum-shun;
cout<<min(shun,ni);
return 0;
}
(一开始把#define int long long注释掉了没发现 结果怎么也过不了……)
未通过中有很大希望的:D、J
D题:
https://ac.nowcoder.com/acm/contest/68444/D
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
if(m>=n||n-m<=n/2) cout<<-1<<endl;
else cout<<m<<" "<<n-m<<endl;
}
}
题解:a=bk+m,b>m,k>=0 //第一句:由
因为a+b=n,所以n=b(k+1)+m
即n>2*m时有解,且我们a=m,b=n-m可为一组解
J题:
https://ac.nowcoder.com/acm/contest/68444/J
我们可以先把每个口罩用的不舒适度极限(即不超过k)的每天的不舒适度存入数组。存完以后,我们将数组sort一下,就得到了从小往大的使用不舒适度排序(因为不舒适度不会减少,所以可以保证再用一次的不舒适度一定是按顺序排列的)。
接下来我们使用while循环,计算使用天数。
//失败版本:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
void solve(){
int n,k;
cin>>n>>k;
int a[N];
vector<int> v;
for(int i=0;a[i];i++)
{
cin>>a[i];
if(a[i]<k) v.push_back(a[i]);//单个口罩初始不舒适度(不超总忍受值的)存入vector
}
int d=0,ans=0;
while(d<=k){//在不超过总值的前提下
sort(v.begin(),v.end());//对现有vector数组元素排序从小到大
d+=v[0];//现有不舒适度加上vector第一个元素也就是最小的那个
ans++;//加完以后相当于天数多了一天
v[0]*=2;//不舒适度最小的情况变为两倍
}
ans-=1;//由于会多算一天所以这里-1
cout<<ans;
}
signed main(){
solve();
return 0;
}
超时主要是因为sort在while里面,导致时间复杂度过高,wa是因为while的条件如果相等是相当于多加了一次,需要在循环外减去或者输出答案时输出ans-1
vector可通过思路:
直接将不超过阈值的翻倍前后的所有可能性一起存入vector数组,然后将整个vector数组从小到大排序,这样就可以直接遍历vector使临时值增加(也就是当前最小的)元素直到达到忍耐上限
#include<iostream>
using namespace std;
const int N=100010;
void solve(){
cin >> n >> k;
vector<int> v;
for(int i = 0; i < n; i ++) {
cin >> a[i];
for(int j = a[i]; j <= k; j = j * 2){
v.push_back(j);
}
}
sort(v.begin(), v.end());
int ans = 0, p = 0;
for(int i = 0; i < v.size(); i ++){
ans += v[i];
if(ans > k){
p = i;
break;
}
}
cout << p;
}
int main(){
solve();
return 0;
}