机试（cs，se）

2017 研究生推免复试机考（计算机系）/ 2017 直升研究生机试

2017 研究生推免复试机考（计算机系） - ECNU Online Judge        ECNU Online Judge

3357. 吉吉木的野望 

Problem #3357 - ECNU Online Judge

思路

因为精度就1e-12，所以不需要跑到1e9就通过了

代码

#include
using namespace std;
#define int long long
signed main()
{
     int d,k;cin>>d>>k;long double sum=0;int maxx=1e7;
     for(int i=min(maxx,k);i>=1;i--){
          sum=1/( (1+(i-1)*d) + sum );
     }
     cout<setprecision(13)<
     sum;
     return 0;
}

3346. 皇后问题

Problem #3346 - ECNU Online Judge

我的思路

问多少个皇后冲突，我记得位运算可做（？），但是我没学

但是普通的模拟+组合数就可以过了

代码

#include
using namespace std;
#define int long long
int ha[100005];
int li[100005];
unordered_map<int,int> zsyx;
unordered_map<int,int> yszx;
signed main()
{
     int ans=0;
     int n;cin>>n;int x,y;
     for(int i=0;i
          cin>>x>>y;
          ha[x]++;li[y]++;
          zsyx[x-y]++;
          yszx[x+y]++;
     }
     for(int i=1;i<100001;i++){
          ans+=ha[i]*(ha[i]-1)/2;
          ans+=li[i]*(li[i]-1)/2;
     }
     for(auto&q:zsyx)
          ans+=q.second*(q.second-1)/2;
     for(auto&q:yszx)
          ans+=q.second*(q.second-1)/2;
     cout<
     return 0;
}

3337. 我认识你

Problem #3337 - ECNU Online Judge

思路

用二进制做，相与为1就是共同好友，用bool装数字，MLE了

#include
using namespace std;
bool g[40001][40001];
int main()
{
     int n,m;cin>>n>>m;int x,y;
     for(int i=0;i
          cin>>x>>y;g[x][y]=1;g[y][x]=1;
     }
     int q;cin>>q;
     for(int i=0;i
          int s,t;cin>>s>>t;
          int ans=0;
          for(int i=1;i<=n;i++){
               ans+=g[s][i]&g[t][i];
          }
          cout<'\n';
     }
}

于是可以用bitset装二进制

但是只改变了装入方式会TLE

#include
using namespace std;
bitset<40004> g[40001];
int main()
{
     int n,m;cin>>n>>m;int x,y;
     for(int i=0;i
          cin>>x>>y;g[x][y]=1;g[y][x]=1;
     }
     int q;cin>>q;
     for(int i=0;i
          int s,t;cin>>s>>t;
          int ans=0;
          for(int i=1;i<=n;i++){
               ans+=g[s][i]&g[t][i];
          }
          cout<'\n';
     }
}

bitset对于二进制的处理速度很快，所以判断 与 之后1的个数可以用bitset装起来再用count

代码

#include
using namespace std;
bitset<40004> g[40001];
int main()
{
     int n,m;cin>>n>>m;int x,y;
     for(int i=0;i
          cin>>x>>y;g[x][y]=1;g[y][x]=1;
     }
     int q;cin>>q;
     for(int i=0;i
          int s,t;cin>>s>>t;
          bitset<40004> ans=(g[s]&g[t]);
          cout<count()<<'\n';
     }
}

3338. 双塔问题

思路

高度尽量高，木块可以舍弃；2的100次方所以dfs不行

用3维的dp，第一维是第i个积木，第二维相差高度，第三维放在塔1还是塔2

代码

#include
using namespace std;
int dp[105][10001][2];//第i个，高度差,放在1还是放在2
int a[105];
int main()
{
     int n;cin>>n;int sum=0;
     memset(dp,-0x3f,sizeof(dp));
     dp[0][0][0]=dp[0][0][1]=0;
     for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}
     sum=sum/2;
     for(int i=1;i<=n;i++){//这是第i个
          for(int j=0;j<=sum;j++){
               for(int k=0;k<2;k++){
                    if(j>=a[i]&&dp[i-1][j-a[i]][k]>=0)
                         dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-a[i]][k]+a[i]);
                         //k高且放在高的
                    if(j-1][a[i]-j][k]>=0)
                         dp[i][j][k]=max(dp[i][j][k],dp[i-1][a[i]-j][k]+j);
                        //k低且放在k，低的变高了,因为抵消了，所以高为j
                    if(dp[i-1][j+a[i]][k]>=0)
                         dp[i][j][k]=max(dp[i][j][k],dp[i-1][j+a[i]][k]);
                        //k低且放在k，高的还是高
                    if(dp[i-1][j][k]>=0)
					dp[i][j][k] = max(dp[i-1][j][k], dp[i][j][k]);//不放积木
               }
          }
     }
     cout<<max(dp[n][0][0],dp[n][0][1]);
}

Problem #3339 - ECNU Online Judge

Problem #3340 - ECNU Online Judge

只有个位数的人通过，算了

*3342. 经典的猜数游戏

Problem #3342 - ECNU Online Judge

*做累了做着玩的

#include
using namespace std;
#define int long long
signed main()
{
    int l=-1e9,r=1e9;string s;
    while(l<=r){
        int mid=(l+r)>>1;
        cout<
        cin>>s;
        if(s=="equal")return 0;
        else if(s=="big")r=mid-1;
        else l=mid+1;
    }
}

3356. 解方程

思路：应该和exgcd有关，但是没做出来，就暴力循环了，有70分

#include
using namespace std;
#define int long long
signed main()
{
     int n,q;cin>>q>>n;int ans=0;
     if(q==1){
          for(int i=1;i<=n;i++){
               if(n%i==0)ans++;
          }
          cout<
     }
     else{
          bool flag=0;
          for(int a = 1;a<=n;a++){
             for(int b = 1;b <= n;b++){
               for(int x = 1; x<=n;x++){
                    for(int y = 1;y<=n ;y++){
                          if(a*x+b*y == n){
                              flag = 1;//标识这个(a,b)对已经完成使命
                              ans++;break;
                          }
                          else if(a*x+b*y>n) break;//直接跳出循环
                    }
                    if(flag==1){flag=0;break;}
               }
            }
          }
          cout<
     }
     return 0;
}

2017 研究生直升面试机考（软件工程）

2017 研究生直升面试机考（软件工程） - ECNU Online Judge

3358. 种水稻

简单的模拟

#include
using namespace std;
#define int long long
signed main()
{
    int T;cin>>T;
    while(T--){int ans=0;
     int n;cin>>n;
     for(int i=0;i
          int x;cin>>x;
          if(x<=10)ans++;
     }
     cout<'\n';
    }
     return 0;
}

B. 泡咖啡 - 2017 研究生直升面试机考（软件工程） - ECNU Online Judge

模拟，不做了

3350. 林吉吉的野望

排序

3352 密集数

就是看数字出现的次数，总和乘次数就可以了

代码

#include
using namespace std;
#define int long long
int G[16];
signed main()
{G[0]=1,G[1]=1;
 for(int i=2;i<16;i++){
     G[i]=G[i-1]*2;
 }
     int T;cin>>T;
     while(T--){
          int n;cin>>n;int sum=0;
          if(n==0){cout<<0<<'\n';continue;}
          for(int i=0;i
               int x;cin>>x;sum+=x;
          }
          cout<
     }
}
 

2018 研究生机试 (计算机系第二批) - ECNU Online Judge

这个看看之后有没有时间写F题