2022年12月7日回文数字

我的答案：思路是将日期转化为数字在判断是否回文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;

#define N  100005
int month[12]={31,29,31,30,31,30,31,31,30,31,30,31};
bool huiwen(string a)
{
    int l = 0,r = a.size()-1;
    while(l<r)
    {
        if(a[l]==a[r])
        {
            l++;
            r--;
        }else
        return false;
    }
    return true;
}
int main()
{
   int a,b,ans;
   cin>>a>>b;
   int y1 = a/10000,y2 = b/10000;
   for(int i =y1;i<=y2;i++)
   {
    for(int j = 0;j<12;j++)
    {
        for(int k = 1;k<=month[j];k++)
        {
            string m,r;
            if(j<10)
             m = '0'+to_string(j);
            else
             m =to_string(j);
            if(k<10)
            r = '0'+to_string(k);
            else
            r = to_string(k);

            string time = to_string(i)+m+r;
            //cout<<stoi(time)<<" ";
            if(huiwen(time))
            {
                if(stoi(time)>=a&&stoi(time)<=b)
                {
                    cout<<time<<" ";
                    ans++;
                }
            }
        }
    }
   }
   cout<<ans;




    return 0;
}

大神解答：只通过模拟月日，判断是否条件范围内并且是回文即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;

#define N  100005
int i,j,n,m,a,b,c,sum,ans;
int s[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=12;i++)//枚举月和日 
        for (j=1;j<=s[i];j++)
        {
            c=(j%10)*1000+
              (j/10)*100+
              (i%10)*10+
              (i/10);//算出前四位。
            sum=c*10000+i*100+j;//算出整个日期 
            if (sum<n||sum>m) continue;
            ans++;//统计 
        }
    printf("%d",ans);
    return 0;
}

奇怪的是我的答案和大神的部分输出输入都相同，不知为何会在结果上报错，有的可能是没考虑到闰年的情况。

12月9日洛谷 P1036选数

看到题其实思路很清晰，就是用DFS，但掌握的不是很好，想写一个用容器的，奈何水平有限呀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;

#define N  100005
int n,k;
int a[25];
long long ans;
bool isprime(int a)//判断是否为素数
{
    for(int i =2;i*i<a;i++)
    {
        if(a%i==0)
         return false;
       
    }
    return true;
}
void dfs(int x,int sum,int flag)//x表示本次dfs开始的下标，sum表示当前总数和，flag控制顺序降重
{
    if(x == k)
    {
        if(isprime(sum))
        ans++;
        return ;
    }
    for(int i =flag;i<n;i++)
    {
        dfs(x+1,sum+a[i],i+1);
    }
    return;
}
int main()
{   
    cin>>n>>k;
    for(int i =0;i<n;i++)
    cin>>a[i];
    dfs(0,0,0);
    cout<<ans;
    return 0;
}

12月10日洛谷P1464 Function

这题看着题目复杂其实只用写个递归函数即可，但是需要注意格式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;

#define W(x,y,z) (w_cnt[x][y][z] ? w_cnt[x][y][z] : w_cnt[x][y][z] = w(x,y,z))
int w_cnt[25][25][25];

int w(int a, int b, int c)
{
    if(a<=0 || b<=0 || c<=0) return 1;
    if(a > 20 || b > 20 || c > 20) return W(20,20,20);
    if(a < b && b < c) return W(a,b,c-1)+W(a,b-1,c-1) - W(a,b-1,c);
    return W(a-1,b,c)+W(a-1,b-1,c)+W(a-1,b,c-1) - W(a-1,b-1,c-1);
}

int main()
{
    int a,b,c;
  while(1){
    cin>>a>>b>>c;
    if(a==-1 && b==-1 && c==-1) break;
      cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<w(a,b,c)<<endl;
  }
}

12月11日P5534 【XR-3】等差数列

题目很简单，但是我一开始读题读错了，以为是求等差数列的低级项，其实只用套数学公式即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;

long long dengcha(long long  a,long long cnt,long long d)
{
    if(cnt==1)
    return a;
    else 
    return (dengcha(a+d,cnt-1,d));
}
int main()
{
   long long a,b,c;
   cin>>a>>b>>c;
   int d = b-a;
   //cout<<dengcha(a,c,d)<<endl;
   long long ans = (dengcha(a,c,d)+a)*c/2;
   cout<<ans;

}

P1192 台阶问题

同样是一看就有思路的题，经典动态规划题目，就是多了个取模的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;

int main()
{
  int n,k;
  cin>>n>>k;
  vector<int> dp(100000);
  dp[0] = dp[1] = 1;//动态规划边界条件
  for(int i = 2;i<=n;i++)
  {
    for(int j =1;j<=k;j++)//可以选择迈开的步数是1~k
    {
        if(i>=j) //楼梯阶数大等于步数才能算一次
        dp[i] = (dp[i]+dp[i-j])%100003;//这一层是由上一层跨1，2，。。。，j步到的，
    }
  }
  cout<<dp[n]%100003;
  return 0;
}

12月12日P1025 [NOIP2001 提高组] 数的划分

有点难度，但感觉之前在leecode上做过，我用了dfs，看了大佬的做法应该还可以用动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
int n,k,sum;
void dfs(int x,int k,int t){
    if(k==1){
        sum++;
        return ;
    }
    for(int i=x;i<=t/k;++i) dfs(i,k-1,t-i);//剪枝
}

int main(){
    cin>>n>>k;
    dfs(1,k,n);
    cout<<sum<<endl;
    return 0;
}

12月13日P4994 终于结束的起点

这题思路也不算太难，就是用求斐波那契数列再加个取模的操作，需要注意的是要用long long，否则会溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
int x;
vector<long long> fb(10000002);
long long f(long long i)
{
    if(fb[i]) return fb[i];
    if(i==0||i==1) return fb[i] = 1%x;
    else
    {
        return fb[i] =(f(i-1)+f(i-2))%x;//斐波那契数列多加了个取模
    }
}
int main(){
    cin>>x;
    long long i =0;
     while(f(i)!=0||f(i+1)!=1)
     i++;
    cout<<i+1;


    return 0;
}

12月15日P1003 [NOIP2011 提高组] 铺地毯

一开始我打算使用模拟暴力解决，但是Memory Limit Exceeded超出内存限制了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
int idx[10005][10005];
int main(){
    memset(idx, -1, sizeof(idx));
    int n;
    cin>>n;
    
    for(int i =0;i<n;i++)
    {
       int a,b,g,k;
       cin>>a>>b>>g>>k;
       for(int i = a;i<a+g;i++)
       {
            for(int j = b;j<b+k;j++)
            {
                idx[i][j] = i+1;
            }
       }
    }   
    int x,y;
    cin>>x>>y;
    cout<<idx[x][y];
   
    return 0;
}

查看了大神的解答发现其实不用模拟，用四个数组分别记录左下角坐标a,b，横坐标g,纵坐标k,然后看x，y是否再这四个值生成的矩形范围内，是的话ans = 层数+1(ans初始值为-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
int idx[10005][10005];
int main(){
    int n;
    cin>>n;
    int a[n],b[n],g[n],k[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i]>>g[i]>>k[i];  //记录每一层的数据
    }
    int x,y;
    cin>>x>>y;
    int ans =-1;
    for(int i=0;i<n;i++)
    {
        if(x>=a[i]&&y>=b[i]&&x<=a[i]+g[i]&&y<=b[i]+k[i])//如果在这个矩形范围内
        ans = i+1;
    }    
   cout<<ans;
    return 0;
}

12月16日P1067 [NOIP2009 普及组] 多项式输出

思路很简单，就是模拟，但是要考虑几种特殊情况如-1和1的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main(){
    int n,x;
    cin>>n;
    for(int i =n;i>=0;i--)//注意要大于等于0
    {
        cin>>x;
        if(x)
        {
            if(i!=n&&x>0) cout<<"+";//是首位的话不加+号
            if(x>1||x<-1||i==0) cout<<x;
            if(x==-1&&i) cout<<"-";
            if(i>1) cout<<"x^"<<i;
            if(i==1) cout<<"x";//特殊情况
        }
    }
    
    return 0;
}

12月17日P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布

模拟就完事了，但是麻烦的是得分数组需要列举出来，直接抄的大佬的了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int vs[5][5] = {{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}}; //得分表的处理 
int n,na,nb;
cin>>n>>na>>nb;
int a[na],b[nb];
for(int i=0;i<na;i++)
cin>>a[i];
for(int i =0;i<nb;i++)
cin>>b[i];
int x,y =0;
for(int i =0;i<n;i++)
{
    x+=vs[a[i%na]][b[i%nb]];//由于按照数组循环所以取模
    y+=vs[b[i%nb]][a[i%na]];
}
cout<<x<<" "<<y<<endl;

12月18日P1563 [NOIP2016 提高组] 玩具谜题

还是很有难度的，一开始想写双向链表了但是发现多少点忘了这些东西了，但是看了看题解没想到其实不用那么复杂，但是这个逆时针的写法确实还是没怎么遇到过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n,m;
    cin>>n>>m;
    vector<string>a;
    vector<int>b;
    for(int i =0;i<n;i++)
    {
        string c;
        int d;
        cin>>d>>c;
        a.push_back(c);
        b.push_back(d);
    }
    int point=0;
    for(int i =0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
       
        
        if(b[point]!=x)//观察归规律，如果方向和左右一样就是顺时针，否则为逆时针
        point = (point+y)%n;
        else
        point =(point-y%n+n)%n;

        
    }
    cout<<a[point];

12月19日P1042 [NOIP2003 普及组] 乒乓球

模拟，但是一次性读入大量数据确实是个盲点，得好好记一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
char str[1000010];//用vector不方便一次性读入大量数据
int cnt =0;//记录总共有多少数据
void show(int n){

    int a=0,b=0;
    for(int i=0;i<cnt;i++){
        if(str[i]=='W') a++;
        if(str[i]=='L') b++;

        if((a>=n||b>=n)&&abs(a-b)>=2){
            cout<<a<<":"<<b<<endl;
            a=b=0;
        }
    }

    //新的一轮刚开始，或上一局没有打完
    cout<<a<<":"<<b<<endl;
}

int main(){
    char ch;

    while(cin>>ch&&ch!='E'){
        if(ch=='W'||ch=='L'){
          str[cnt++]=ch;
        }
    }

    show(11);
    cout<<endl;
    show(21);
}

12月20日P1179 [NOIP2010 普及组] 数字统计

入门题，很简单直接c++ 字符串count秒了

1
2
3
4
5
6
7
8
9
10
int m,n;
   cin>>m>>n;
   int ans =0;
   for(int i=m;i<=n;i++)
   {
       auto a = to_string(i);
       int x = count(a.begin(),a.end(),'2');
       ans+=x;
   }
   cout<<ans;

12月21日P2615 [NOIP2015 提高组] 神奇的幻方

思路清晰，直接模拟。细节还是得多注意哦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int n,a[40][40],x,y;
int main(){
    cin>>n;
    int cnt =1;
    a[0][n/2] =1 ;
    x =0,y =n/2;
    for(int i =2;i<=n*n;i++)
    {
        if(x==0&&y!=n-1) a[n-1][y+1] =i,x =n-1,y++;
        else if(y==n-1&&x!=0) a[x-1][0] =i,x--,y =0;
        else if(x==0&&y==n-1) a[x+1][y] =i,x++;
        else if(x!=0&&y!=n-1)
        {
            if(a[x-1][y+1] ==0&&x-1>=0&&y+1<=n) a[x-1][y+1] =i,x=x-1,y =y+1;
            else a[x+1][y] =i,x++;
        }
       

        
    }
    for(int i=0;i<n;i++)
    {
        for(int j =0;j<n;j++)
        {
            cout<<a[i][j];
            if(j == n-1) cout<<endl;
            else cout<<" ";
        }
    }
    return 0;
}

12月23日P1059 [NOIP2006 普及组] 明明的随机数

set直接秒了，看来stl容器还是忘了不少

1
2
3
4
5
6
7
8
9
10
11
12
13
int n;
   cin>>n;
   set<int>a;
   for(int i=0;i<n;i++)
   {
       int b;
       cin>>b;
       a.insert(b);
   }    
   cout<<a.size();
   cout<<endl;
   for(int i:a)
   cout<<i<<" ";

P1068 [NOIP2009 普及组] 分数线划定](https://www.luogu.com.cn/problem/P1068))
题目很有特色，构造结构体来解题是我第一次见，确实比哈希表方便些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct grace 
{
    int a;
    int b;//考号
};
bool cmp(grace a,grace b)
{
    if(a.a>b.a) return 1;
    if(a.a==b.a&&a.b<b.b)return 1;

    return 0;
}
grace fen[5000];  
int main()
{
     int n,m;
     cin>>n>>m;
     for(int i=0;i<n;i++)
     cin>>fen[i].b>>fen[i].a;
     sort(fen,fen+n,cmp);
     int last =fen[m*3/2-1].a;
     int cnt =0;
     for(int i =0;i<n;i++)
     if(fen[i].a>=last) cnt++;
     cout<<last<<" "<<cnt<<endl;//不能用m = m*1.5来代替last
     for(int i =0;i<cnt;i++)
     {
        cout<<fen[i].b<<" "<<fen[i].a<<endl;
     }
     return 0;
}

12月24日P1051 [NOIP2005 提高组] 谁拿了最多奖学金

题目挺简单的，但是写法借鉴了大神的，更加简洁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n,score1,score2,sum=0,max_g=0,total=0,paper;
    char gan,xi;
    string name,max_n;
    cin>>n;
    for(int i =0;i<n;i++)
    {
        cin>>name>>score1>>score2>>gan>>xi>>paper;
        if(score1>80&&paper>0) sum+=8000;
        if(score1>85&&score2>80) sum+=4000;
        if(score1>90) sum+=2000;
        if(score1>85&&xi=='Y') sum+=1000;
        if(score2>80&&gan=='Y') sum+=850;
        total +=sum;
        if(sum>max_g)
        {
            max_n =name;
            max_g = sum;
        }
        sum=0;

    }
    cout<<max_n<<endl<<max_g<<endl<<total;

除了这题还做了Acwing的孤独的照片，但是没读懂就cv了