头像

fanfande




离线:9小时前



fanfande
9小时前
#include<iostream>
#include<string>
using namespace std;
const int N=40;
int n;
int pre[N],post[N];

int dfs(int l1,int r1,int l2,int r2,string &in )
{
    if(l1>r1) return 1;
    if(pre[l1]!=post[r2]) return 0;

    int cnt=0;
    for(int i=l1;i<=r1;i++)
    {
        string lin,rin;
        int lcnt=dfs(l1+1,i,l2,l2+i-l1-1,lin);
        int rcnt=dfs(i+1,r1,l2+i-l1-1+1,r2-1,rin);

        if(lcnt&&rcnt)
        {
            in=lin+to_string(pre[l1])+' '+rin;
            cnt+=lcnt*rcnt;
            if(cnt>1) break;
        }
    }
    return cnt;
}

int main()
{
    cin>>n;

    for(int i=0;i<n;i++) cin>>pre[i];
    for(int i=0;i<n;i++) cin>>post[i];

    string in;

    int cnt=dfs(0,n-1,0,n-1,in);

    if(cnt>1) puts("No");
    else puts("Yes");
    in.pop_back();
    cout<<in<<endl;
    return 0;
}


活动打卡代码 AcWing 1646. 谷歌的招聘

#include<iostream>
#include<string>
using namespace std;
const int N=1010;
string a;
int l,k;
int prime[]

bool is_prime(int x)
{
    if(x<2) return false;
    for(int i=2;i*i<=x;i++)
        if(!(x%i))
            return false;
    return true;
}
int main()
{
    cin>>l>>k>>a;
    for(int i=0;i+k<=l;i++)
    {
        int t=stoi(a.substr(i,k));
        if(is_prime(t)) 
        {
            cout<<a.substr(i,k)<<endl;
            return 0;
        }
    }
    cout<<"404"<<endl;
    return 0;
}


活动打卡代码 AcWing 1606. C 语言竞赛

#include<iostream>
#include<unordered_map>
using namespace std;
const int N=1e4+10;
unordered_map<string,int>  list;
int n,q;

bool is_prime(int x)
{
    if(x<2) return false;
    for(int i=2;i*i<=x;i++)
        if(!(x%i))  return false;

    return true;
}

int main()
{
    cin>>n;

    for(int i=0,idx=1;i<n;i++)
    {
        string a;
        cin>>a;
        list[a]=idx++;
    }

    cin>>q;
    for(int i=0;i<q;i++)
    {
        string a;
        cin>>a;
        cout<<a<<": ";
        if(list.find(a)==list.end()) cout<<"Are you kidding?"<<endl;
        else
        {
            int t=list[a];
            if(t==1)  cout<<"Mystery Award"<<endl;
            else if(t==0)  cout<<"Checked"<<endl;
            else if(is_prime(t))  cout<<"Minion"<<endl;
            else
            {
                cout<<"Chocolate"<<endl;
            }

            list[a]=0;
        }

    }
    return 0;
}


活动打卡代码 AcWing 1602. 卡住的键盘

#include<unordered_set>
#include<iostream>
using namespace std;
unordered_set<char>  work,broken;
int main()
{
    int n;
    string s;
    cin>>n>>s;

    for(int i=0;i<s.size();i++)
    {
        int cnt=1;
        int c=s[i];
        while(s[i]==s[i+1]) i++,cnt++;
        if(cnt%n)  
            if(!work.count(c))  work.insert(c);
    }

    for(int i=0;i<s.size();i++)
    {
        if(work.count(s[i])) continue;
        if(!broken.count(s[i]))  broken.insert(s[i]);
    }
    unordered_set bro=broken;
    for(int i=0;i<s.size();i++)
    {
        if(bro.count(s[i])) cout<<s[i],bro.erase(s[i]);
    }
    cout<<endl;

    for(int i=0;i<s.size();)
    {
        cout<<s[i];
        if(broken.count(s[i]))  i+=n-1;
        i++;
    }
    return 0;
}



图形学依赖线性代数,微积分,光学,力学,信号处理,数值分析。

向量运算:
默认列向量
dot multi点乘:
1.用来找到两个方向之间的夹角,
2.找到一个向量投影到另一个向量的大小(有利于向量的分解)
3.判断两个向量有多么接近,或者判断前后

cross 叉乘:
右手法则,、a×b=||a||×||b||*sin ;
1.找到 Z 轴
2.向量的左和右,内和外

Matrices
实现变换

transformation (modeling and viewing)
scale 缩放;

homogeneous coordiante 齐次坐标

平移操作 非线性
使用齐次坐标,在二维基础上增加一个数
2D point (x,y,1);
2D vector (x,y,0);
区分点和向量,向量具有平移不变性;

根据w判断
vector + vector= vector;
point - point = vector;
point + vector= point;
point + point = 两个点的中点

affine transformation 都可以用齐次变换



活动打卡代码 AcWing 1594. 数段之和

#include<iostream>
using namespace std;
const int N=1e5+10;
long double a[N];

int main()
{
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)   cin>>a[i];

    long double res=0;

    for(int i=1;i<=n;i++)
    {
        res+=a[i]*i*(n-i+1);
    }
    printf("%.2llf",res);
    return 0;
}



活动打卡代码 AcWing 1593. 整数分解

#include<iostream>
#include<cstring>
using namespace std;
const int N=410;
int f[21][N][N];

int power(int a,int b)
{
    int res=1;
    for(int i=0;i<b;i++)
      res*=a;
    return res;
}

int main()
{
    int n,k,p;
    cin>>n>>k>>p;

    memset(f,-0x3f,sizeof f);
    f[0][0][0]=0;

    int m;//前m个数
    for(m=1;;m++)
    {
        int v=power(m,p);
        if(v>n) break;

        for(int i=0;i<=n;i++)
            for(int j=0;j<=k;j++)
            {
                f[m][i][j]=f[m-1][i][j];
                if(i>=v&&j)f[m][i][j]=max(f[m][i][j],f[m][i-v][j-1]+m);
            }
    }
    m--;

    if(f[m][n][k]<0)  puts("Impossible");
    else
    {
        printf("%d = ",n);
        bool isfirst=true;
        while(m)
        {
            int v=power(m,p);
            while(n>=v && k && f[m][n-v][k-1]+m==f[m][n][k])
            {
                if(isfirst)  isfirst=false;
                else cout<<" + ";

                printf("%d^%d",m,p);
                n-=v,k--;
            }
            m--;
        }

    }
    return 0;
}


活动打卡代码 AcWing 1586. 连续因子

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int start=0,res=0;
   for(int i=2;i*i<=n;i++)
   {
       int k=i,cnt=0;
       int mul=k;
       while(!(n%mul))
       {
           mul*=++k;
           cnt++;
       }

       if(cnt>res)
       {
           res=cnt;
           start=i;
       }
   }
   if(start==0) 
      cout<<'1'<<"\n"<<n<<endl;
   else 
      {
         cout<<res<<"\n";
         cout<<start++;
         for(int i=0;i<res-1;i++)
         {
             cout<<'*'<<start++;
         }
      }
    return 0;
}



fanfande
16天前

题目全部来自于 LeetCode的简单题 ,然后第三题没考虑到下标为负对数组无意义,但当时在acwing 上还是oj出了像样的结果,可能是不同编译器的原因。
可以考虑将j下标右移来使下标合法。


今年复旦的三道题相当简单,可能是开卷的原因。推测对复试结果的影响应该不大
不确定对不对
屏幕截图 2021-03-29 153058.png

考点:数组模拟二叉树
我们可以用一个数组 a[ ] 来模拟这个完全二叉树,下标从 1 开始 ;
对于下标为 i 的结点,其 左孩子下标为 2i,右孩子为 2i + 1;
利用这个性质先读入二叉树,再顺序遍历这个数组 ;
如果当前结点大于等于父节点,cnt++;
否则更新该结点的值为其父节点的值;

#include<iostream>
#include<string>
using namespace std;
const int N=10010;
int tree[N],idx=1;

int main()
{
     string a;
     while(cin>>a)
     {
         if(a=="null")  
         {
             continue;
             idx++;
         }

         int x=stoi(a);
         tree[idx++]=x;
     }

     int ans=0;
     for(int i=1;i<idx;i++)
     {
         if(tree[i]>=tree[i/2])   ans++;
         else  tree[i]=tree[i/2];
     }

     cout<<ans<<endl;
     return 0;
}

屏幕截图 2021-03-29 153236.png
考点: dp 问题;
到达第 i 个台阶的最后一步一共有两种情况,(两步或者一步)
写出状态转移方程: f[i]=f[i-1]+f[i-2]
确定初始状态 : f[1]=1,f[2]=2;
从 3 开始 维护结果数组 f[]
时间复杂度 O(N) ;

#include<iostream>
using namespace std;
const int N=100100;
long long  f[N];


int main()
{
    int n;
    cin>>n;

    f[1]=1,f[2]=2;

    for(int i=3;i<=n;i++)
       f[i]=f[i-1]+f[i-2];
    cout<<f[n]<<endl;
    return 0;
}

屏幕截图 2021-03-29 153346.png
考点:还是 Dp 问题
f[i][j] 表示 对于序列的前 i 个数,取得期望值 j 的方法的总数;
类似上一题,讨论第 i 个数 的取法,可以有 取正 和 取负 两种状态;
写出状态转移方程: f[i][j]=f[i-1][j-a[i]]+f[i-1][j+a[i]]
初始状态: f[1][a[1]]=1,f[1][-1*a[1]]=1;
注意 j 在转态转移过程中会取到负值,故过程中 j 从 -sum 维护到 +sum;
优化方法:滚动数组优化,降低空间复杂度
时间复杂度 O(N^2)

#include<iostream>
using namespace std;
const int N=10010;
int f[N][N];
int a[N],idx=1;
int sum;
int E;
int main()
{
    cin>>E;
    while(cin>>a[idx])
        sum+=a[idx++];       

    f[1][a[1]]=1,f[1][-1*a[1]]=1;

    for(int i=2;i<idx;i++)
    {
        for(int j=-1*sum;j<=sum;j++)
        {
            f[i][j]=f[i-1][j-a[i]]+f[i-1][j+a[i]];
        }
    }

    cout<<f[idx-1][E]<<endl;
    return 0;
}


活动打卡代码 AcWing 1629. 延迟的回文数

fanfande
17天前
#include<iostream>
#include<algorithm>
using namespace std;

bool check(string a)
{
    int n=a.size()-1;
    for(int i=0;i<(n+1)>>1;i++)
    {
        if(a[i]!=a[n-i])  return false ;
    }
    return true;
}

int main()
{
    string a;
    cin>>a;
    int cnt=0;
    while(!check(a))
    {

        string b;
        int t=0,n=a.size()-1;
        for(int i=0;i<a.size();i++)
        {
            int x=a[i]-'0'+a[n-i]-'0'+t;
            b=to_string(x%10)+b;
            t=x/10;
        }
        if(t==1)  b='1'+b;
        cout<<a<<' '<<'+';
        reverse(a.begin(),a.end());
        cout<<' '<<a<<' '<<'='<<' ';
        a=b;
        cout<<a<<endl;
        cnt++;

        if(cnt>9)  break;
    }

    if(check(a))  cout<<a<<" is a palindromic number."<<endl;
    else  printf("Not found in %d iterations.",cnt);
    return 0;
}