8.21-东塘-401-下午-陈-训练

· · 个人记录

U370610 回文串

这道题直接用常规实现回文操作 判断前后对称位置是否相同（回文定义）

#include<bits/stdc++.h>
using namespace std;
string s;
int n;
const int maxn=1e5+10;
char a[maxn];
char b[maxn];
//123456

//12345  5/2=2
bool huiwen(string s){
    int len=s.size()-1;
    for(int i=1;i<=len;i++){
        if(s[i]!=s[len-i+1]){
            return 0;
        }
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s>>n;
    s='#'+s;
    while(n--){
        int x;
        char c;
        cin>>x>>c;
        s[x]=c;
//      cout<<s;
        if(huiwen(s)){
            cout<<"Yes"<<'\n';
        }else{
            cout<<"No"<<'\n';
        } 
    }
    return 0;
}

但是不能拿满分可以稍微优化一下 可以前后不判重复

bool huiwen(string s){
    int len=s.size()-1;
    for(int i=1;i<=len/2;i++){
        if(s[i]!=s[len-i+1]){
            return 0;
        }
    }
    return 1;
}

U372270 17的时间串

进制处理我首先打了暴力

进制处理有一点忘记了

但后面通过模拟我有思路了

但时间不够了 最后交卷没写完

后面用自己的思路写完就AC了

比较可惜 基础不牢固

（我过了也可能数据水了）

我直接在二进制上处理

我想的是乘法分配律

十进制乘17

相当与二进制每一位乘17

所以我就在乘完一个个进位

#include<bits/stdc++.h>
using namespace std;
#define int long long 
string s;
int x;
// 10011
int cnt=1;
const int maxn=1e6+10;
int a[maxn];
int b[maxn];
signed main(){
    cin>>s;
//  for(int i=s.size()-1;i>=0;i--){
//      x+=(s[i]-'0')*cnt;
//      cnt*=2;
//  }
//  x*=17;
//  int cnt=0;
    int tmp=0;
    for(int i=s.size()-1;i>=0;i--){
        tmp++;
        a[tmp]=(s[i]-'0')*17;
    }
    for(int i=1;i<=1e5;i++){
        if(a[i]>1){
            a[i+1]+=a[i]/2;
            a[i]%=2;
        }
//      cout<<a[i];
    }
    bool flag=0;
    int cnt=0;
    for(int i=tmp+1e5;i>=1;i--){
        if(a[i]==0&&flag==0){
            continue;
        }else {
            flag=1;
        }
        cnt++;
        b[cnt]=a[i];
    }
    for(int i=1;i<=cnt;i++){
        cout<<b[i];
    }
    return 0;
}

U550993 数对问题-基础版

这道题我也是先拿了暴力分

枚举i和j 然后判断题目条件

直接使用了自带__gcd（）

拿了30pts

正解考试没想出来 

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
bool zhi(int x){//质数判断
    if(x<=1){
        return 0;
    }
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return 0;
    }
    return 1;
}
signed main(){
    cin>>t;
    while(t--){
        int n,cnt=0;
        cin>>n;
        for(int i=2;i<=n;i++){
            for(int j=2;j<=n;j++){//暴力枚举
                if(zhi(i/__gcd(i,j))&&zhi(j/__gcd(i,j))){//判断题目条件
                    cnt++;
                }
            }
        }
        cout<<cnt<<'\n';
    }
    return 0;
}

正解

有两种情况

第一种 i和j自己本身就是质数

第二种 i和j都是某个指数的k倍 k=__gcd(i,j);

从第二种可以得知可以运用埃氏筛

正解

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
bool vis[maxn];
int N=1e6;
int cnt=0;
int primes[maxn];
void aishishai(){
    vis[0]=vis[1]=1;
    for(int i=2;i<=N;i++){
        if(vis[i]==0){
            primes[cnt++]=i;
            for(int j=i+i;j<=N;j+=i){
                vis[j]=1;
            }
        }
    }
    return ;
}
struct ANS{
    int n,val;
    int id;
    bool operator<(const ANS &rhs)const {
        return n<rhs.n;
    }
}ans[maxn];
long long outp[maxn];
int main(){
    aishishai();
    cnt--;
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>ans[i].n ;
        ans[i].id=i;
    }
    sort(ans+1,ans+t+1);
    int pos=0;
    for(int i=1;i<=t;i++){
        while(pos+1<=cnt&&primes[pos+1]<=ans[i].n){
            pos++;
        }
        long long sum=0;
        for(int j=0;j<=pos;j++){
            long long xx=ans[i].n/primes[j];
            sum+=xx*j;
        }
        sum*=2;
        outp[ans[i].id ]=sum;
    }
    for(int i=1;i<=t;i++){
        cout<<outp[i]<<'\n';
    }
    return 0;
}