首页 > 代码库 > Summer training #8

Summer training #8

2024-10-29 05:14:01   265人阅读

A：

B：按题意直接暴力找符合题意的数的个数

技术分享 
#include <bits/stdc++.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#define foror(i,a,b) for(i=a;i<b;i++)
#define foror2(i,a,b) for(i=a;i>b;i--)
#define EPS 1.0e-6
#define PI acos(-1.0)
#define INF 3000000000
#define MOD 1000000009
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
//using ll = long long;
//using ull= unsigned long long;
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
typedef long long ll;
int num[15][2];//+ 1 - 2 * 3 / 4
int main()
{
 //freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 int n;
 string a;
 int ans=0;
 cin >> n;
 int now;
 for(int i=1;i<=n;i++)
 {
        cin >> a >> now;
        num[i][1]=now;
        if(a[0]==‘A‘)
        num[i][0]=1;
        if(a[0]==‘S‘)
        num[i][0]=2;
        if(a[0]==‘M‘)
        num[i][0]=3;
        if(a[0]==‘D‘)
        num[i][0]=4;
 }
 for(int i=1;i<=100;i++)
 {
        int cur=i;
        for(int j=1;j<=n;j++)
        {
        if(num[j][0]==1)
        {
        cur+=num[j][1];
        }
        if(num[j][0]==2)
        {
        cur-=num[j][1];
        if(cur<0)
        {
        ans++;
        break;
        }
        }
        if(num[j][0]==3)
        {
        cur*=num[j][1];
        }
        if(num[j][0]==4)
        {
        if(cur%num[j][1]!=0)
        {
        ans++;
        break;
        }
        else
        cur/=num[j][1];
        }
        }
 }
 cout<<ans<<endl;
  return 0;
}
View Code

C：水

D：s[i][j]可以向四个方向跳s[i][j]个格子 问能不能从左上角跳到右下角 BFS

技术分享 
#include <bits/stdc++.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#define foror(i,a,b) for(i=a;i<b;i++)
#define foror2(i,a,b) for(i=a;i>b;i--)
#define EPS 1.0e-6
#define PI acos(-1.0)
#define INF 3000000000
#define MOD 1000000009
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
//using ll = long long;
//using ull= unsigned long long;
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
typedef long long ll;
int dir[5][2];
int m,n;
char s1[505][505];
int  a[505][505];
int ans[505][505];
int flag=0;
pair<int,int> now;
queue<pair<int,int> > que;
void bfs()
{
 for(int i=0;i<=500;i++)
        for(int j=0;j<=500;j++)
        ans[i][j]=2e9;
 ans[1][1]=0;
 int dx,dy;
 while(!que.empty())
 {
        now=que.front();
        que.pop();
        int f=now.first;
        int s=now.second;
        int j=a[f][s];
        for(int i=0;i<4;i++)
        {
        dx=f+j*dir[i][0];
        dy=s+dir[i][1]*j;
        if(dx>=1&&dx<=m&&dy>=1&&dy<=n&&ans[dx][dy]>ans[f][s]+1)
        {
        ans[dx][dy]=ans[f][s]+1;
        now.first=dx,now.second=dy;
        que.push(now);
        }
        }
 }
}
int main()
{
 //freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 cin >> m >> n;
dir[0][0]=-1,dir[0][1]=0;
dir[1][0]=1,dir[1][1]=0;
dir[2][0]=0,dir[2][1]=1;
dir[3][0]=0,dir[3][1]=-1;
 for(int i=1;i<=m;i++)
 {
        scanf("%s",s1[i]+1);
        for(int j=1;j<=n;j++)
        a[i][j]=s1[i][j]-‘0‘;
 }
 /*for(int i=0;i<m;i++)
 {
        for(int j=0;j<n;j++)
        printf("%d",a[i][j]);
        cout<<endl;
 }*/
 //TS;
 now.first=now.second=1;
 que.push(now);
 bfs();
 //TS;
 if(ans[m][n]==2e9)
 cout<<"IMPOSSIBLE"<<endl;
 else
 cout<<ans[m][n]<<endl;
  return 0;
}
View Code

E：水 

F：水

G：水

H：加权区间调度问题 瞎DP

技术分享 
#include <bits/stdc++.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#define foror(i,a,b) for(i=a;i<b;i++)
#define foror2(i,a,b) for(i=a;i>b;i--)
#define EPS 1.0e-6
#define PI acos(-1.0)
#define INF 3000000000
#define MOD 1000000009
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
//using ll = long long;
//using ull= unsigned long long;
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
typedef long long ll;
struct wave
{
ll start;
ll w;
ll t;
ll end;
}now[300005];
bool cmp(wave a,wave b)
{
return a.start>b.start;
}
ll dp[1000010];
int main()
{
 //freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 int n;
 ll maxn=0;
 cin >> n;
 for(int i=1;i<=n;i++)
 {
        int t;
        scanf("%d %d %d",&now[i].start,&now[i].w,&now[i].t);
        now[i].end=now[i].t+now[i].start;
        maxn=max(maxn,now[i].end);
 }
 sort(now+1,now+1+n,cmp);
 int pop=1;
 for(int i=1000000;i>=1;i--)
 {
        if(i==now[pop].start)
        {
        if(i+now[pop].t>1000000)
        dp[i]=max(dp[i+1],now[pop].w);
        else
        dp[i]=max(dp[i+1],dp[i+now[pop].t]+now[pop].w);
        pop++;
        }
        else
        dp[i]=dp[i+1];
 }
 cout<<dp[1]<<endl;
  return 0;
}
View Code

J：每个格子的值为其为中心九宫格之和 问最终的值 其实一起都要除九的话就不用除了

技术分享 
#include <bits/stdc++.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#define foror(i,a,b) for(i=a;i<b;i++)
#define foror2(i,a,b) for(i=a;i>b;i--)
#define EPS 1.0e-6
#define PI acos(-1.0)
#define INF 3000000000
#define MOD 1000000009
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
//using ll = long long;
//using ull= unsigned long long;
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
typedef long long ll;
int now[110][110];
int doit[110][110];
set<int> ans;
int main()
{
 //freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 int m,n,time;
 cin >> m >> n >> time;
 for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        scanf("%d",&now[i][j]);
 while(time--)
 {
        mem(doit,0);
        for(int i=0;i<n;i++)
        {
                for(int j=0;j<m;j++)
                {
                        
                        
                        for(int x=-1;x<=1;x++)
                        {
                                for(int y=-1;y<=1;y++)
                                {
                                int dx=(n+i+x)%n;
                                int dy=(m+j+y)%m;
                                doit[i][j]+=now[dx][dy];
                                }
                        }
                }
        }
        for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                        now[i][j]=doit[i][j];
 }
 for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
                ans.insert(now[i][j]);
 cout<<ans.size()<<endl;
  return 0;
}
View Code

K：DFS+回溯 注意！！！每个轮子只能有一个旋转状态 如果发生矛盾了就转不动了！

技术分享 
#include <bits/stdc++.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#define foror(i,a,b) for(i=a;i<b;i++)
#define foror2(i,a,b) for(i=a;i>b;i--)
#define EPS 1.0e-6
#define PI acos(-1.0)
#define INF 3000000000
#define MOD 1000000009
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
//using ll = long long;
//using ull= unsigned long long;
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
typedef long long ll;
int n;
int flag=-1;
struct point
{
int x,y,r;
}a[1005];
vector<int> v[1005];
int visit[1005];
int ans=0;
int anser;
bool check(point a,point b)
{
int dx=abs(a.x-b.x);
int dy=abs(a.y-b.y);
int dr=a.r+b.r;
if(dx*dx+dy*dy==dr*dr)
 return true;
 return false;
}
void dfs(int num,int now)
{
        if(flag==1)
        return ;
        for(int i=0;i<v[num].size();i++)
        {
        int next=v[num][i];
        if(flag==1)
        return ;
        if(visit[next]==-1)
        {
        visit[next]=now;
        dfs(next,now^1);
        }
        if(visit[next]!=now)
        {
        flag=1;
        return ;
        }
        }
}
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main()
{
 //freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 cin >> n;
 mem(visit,-1);
 visit[1]=0;
 for(int i=1;i<=n;i++)
 {
        cin >> a[i].x >> a[i].y >> a[i].r;
 }
 for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
 {
        if(check(a[i],a[j]))
        {
        v[i].push_back(j);
        v[j].push_back(i);
        }
 }
 dfs(1,1);
 if(flag==1)
 {
        cout<<"The input gear cannot move."<<endl;
        return 0;
 }
 if(visit[n]==-1)
 {
        cout<<"The input gear is not connected to the output gear."<<endl;
        return 0;
 }
        int chu=gcd(a[1].r,a[n].r);
        if(visit[1]!=visit[n])
        cout<<"-";
        printf("%d:%d\n",a[1].r/chu,a[n].r/chu);
  return 0;
}
View Code

 

Summer training #8


联系
我们