总结
A. 小W的病毒歼灭战
思路
一道简单的模拟题，用队列来模拟换弹夹的过程，用一个标记数组来记录那些在队列中。
注意的点
十年OI一场空，不开long long见祖宗
代码
#include<bits/stdc++.h>
using namespace std;
int ans[1010];
queue<int> a;
int main(){
freopen("bd.in","r",stdin);
freopen("bd.out","w",stdout);
int n,m;
cin>>m>>n;
long long us=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(ans[x]==0){
us++;
ans[x]++;
a.push(x);
if(a.size()>m){
ans[a.front()]--;
a.pop();
}
}
}
cout<<us;
return 0;
}
B. 小田的三倍数
思路
在一年级学过，3的倍数特征：在所有位数相加时也是3的倍数，就是3的倍数
所以用字符串遍历一遍，将所有位数相加，向3取余，就是结果
注意的点
字符串要-'0'，不要搞混i与j。
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("three.in","r",stdin);
freopen("three.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int op=0;
for(int i=1;i<=n;i++){
string u;
cin>>u;
//cout<<u<<endl;
for(int j=0;j<u.size();j++){
op+=u[j]-'0';
//cout<<u[j]<<" "<<op<<" "<<u<<endl;
}
}
//cout<<endl;
if(op%3==0){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}
小田的省钱计划
思路
这一题第一眼是双指针，但其实是道前缀和与枚举的题目，其中参杂了一些DP思想。
用f[i]表示从一到i最省钱的方案，所以可以得到递推式
注意的点
long long
代码
#include<bits/stdc++.h>
using namespace std;
long long a[100010],s[100010];
int main(){
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]-=m;
if(s[i-1]<0){
s[i]=a[i];
}else{
s[i]=s[i-1]+a[i];
}
}
long long ans=0;
for(int i=1;i<=n;i++){
ans=max(s[i],ans);
}
cout<<ans;
return 0;
}
D. 计算表达式的值
纯模板
代码
#include<bits/stdc++.h>
using namespace std;
stack<int> a;
stack<char> op;
unordered_map<char,int> mp;
void add(){
int sum2=a.top();a.pop();
int sum1=a.top();a.pop();
char up=op.top();op.pop();
int t=0;
if(up=='+'){
t=sum1+sum2;
}
if(up=='-'){
t=sum1-sum2;
}
if(up=='*'){
t=sum1*sum2;
}
if(up=='/'){
t=sum1/sum2;
}
if(up=='^'){
t=1;
for(int i=1;i<=sum2;i++){
t=sum1*t;
}
}
a.push(t);
}
int main(){
freopen("bds.in","r",stdin);
freopen("bds.out","w",stdout);
mp['+']=1;
mp['-']=1;
mp['*']=2;
mp['/']=2;
mp['^']=3;
string u;
getline(cin,u);
for(int i=0;i<u.size();i++){
//cout<<i<<" ";
if(isdigit(u[i])){
int sum=0,j=i;
while(isdigit(u[j])&&j<u.size()){
sum=sum*10+u[j]-'0';
j++;
//cout<<sum<<" "<<j<<endl;
}
i=j-1;
a.push(sum);
}else if(u[i]=='('){
op.push('(');
}else if(u[i]==')'){
while(op.top()!='('){
add();
}
op.pop();
}else{
while(op.size()&&op.top()!='('&&mp[op.top()]>=mp[u[i]]){
add();
}
op.push(u[i]);
}
}
while(op.size()){
add();
}
cout<<a.top();
return 0;
}
E. 永夜的报应
思路
我们上课时得知，异或就是没有进位的加法，所以最优解是全部异或
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("huiye.in","r",stdin);
freopen("huiye.out","w",stdout);
int n;
cin>>n;
long long ans=0;
int x;
cin>>x;
ans=x;
for(int i=2;i<=n;i++){
cin>>x;
ans=ans^x;
}
cout<<ans;
return 0;
}
F. 数学题2
思路
找出所有的约数，再计算约数中最大的，循环找到>=k的，再输出
代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp;
int up=0;
void st(int x){
mp[1]++;
if(x!=1){
mp[x]++;
}
up=max(up,x);
int i;
for(i=2;i<=x/i;i++){
if(x%i==0){
mp[i]++;
if(x/i!=i){
mp[x/i]++;
}
}
}
}
int main(){
freopen("math2.in","r",stdin);
freopen("math2.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
st(x);
}
int as=up;
for(int i=1;i<=n;i++){
for(int j=as;j>=1;j--){
if(mp[j]>=i){
as=j;
cout<<j<<endl;
break;
}
}
}
return 0;
}
