开启辅助访问 切换到宽版

奇迹创客社区

 注册
 登录
搜索
热搜: NOIP OIer 神牛
信息学基地社区»论坛 › 青少年信息学 › 信息学奥赛 › OJ题解 › CSP-J 10月模拟赛标程
返回列表 发新帖
查看: 392|回复: 4

CSP-J 10月模拟赛标程

[复制链接]
魏晟伦

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
发表于 2021-10-22 16:21:14 | 显示全部楼层 |阅读模式
本帖最后由 魏晟伦 于 2021-10-22 16:21 编辑

T1（优化版）
  1. #include<bits/stdc++.h>
  2. #define endit printf("-1\n");return 0
  3. using namespace std;
  4. int sureans=10001,minans,n;
  5. char c[10001],v;
  6. int main(){
  7.         //freopen("paint.in","r",stdin);
  8.         //freopen("paint.out","w",stdout);
  9.         cin>>n;
  10.         for (int i=0;i<n;i++)
  11.                 cin>>c[i];
  12.         for (int i=0;i<n;i++){
  13.                 cin>>v;
  14.                 if (c[i]>v){
  15.                     endit;
  16.                 }
  17.                 if (v<'Z')
  18.                     if (v-c[i]!=sureans&&sureans<10001){
  19.                         endit;
  20.                     }
  21.                     else
  22.                         sureans=v-c[i];
  23.                 else
  24.                     minans=max(minans,v-c[i]);
  25.         }
  26.         if (sureans<minans){
  27.             endit;
  28.         }
  29.         if (sureans==10001)
  30.             sureans=minans;
  31.         printf("%d\n",sureans*n);
  32.         //fclose(stdin);
  33.         //fclose(stdout);
  34.         return 0;
  35. }
复制代码


回复

使用道具 举报

魏晟伦

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
 楼主| 发表于 2021-10-22 16:22:51 | 显示全部楼层
T1（朴素版）
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. string s1,s2;
  5. bool check(string s1,string s2){
  6.     for (int i=0;i<n;i++)
  7.         if (s1[i]!=s2[i])
  8.             return false;
  9.     return true;
  10. }
  11. void add(string &s){
  12.     for (int i=0;i<n;i++)
  13.         s[i]=(s[i]<'Z')?s[i]+1:'Z';
  14. }
  15. int main(){
  16.     cin>>n;
  17.     cin>>s1>>s2;
  18.     for (int i=0;i<26;i++){
  19.         if (check(s1,s2)){
  20.             cout<<i*n<<endl;
  21.             return 0;
  22.         }
  23.         add(s1);
  24.     }
  25.     cout<<-1<<endl;
  26.     return 0;
  27. }
复制代码


两个代码都可以通过。
回复

使用道具 举报

魏晟伦

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
 楼主| 发表于 2021-10-22 16:26:56 | 显示全部楼层
T2
  1. #include<bits/stdc++.h>
  2. #define map mapp
  3. using namespace std;
  4. int N,L,x,y,ans;
  5. bool map[405][405];
  6. inline int dis(int x1,int y1,int x2,int y2){
  7.         return abs(x1-x2)+abs(y1-y2);
  8. }
  9. int main(){
  10.     //freopen("cover.in","r",stdin);
  11.     //freopen("cover.out","w",stdout);
  12.         cin>>N>>L;
  13.         for (int i=1;i<=N;i++){
  14.                 scanf("%d%d",&x,&y);
  15.                 map[x][y]=true;
  16.         }
  17.         for (int i=0;i<401;i++){
  18.                 for (int j=0;j<401;j++){
  19.                         int minx=max(0,i-L),maxx=min(400,i+L),miny=max(0,j-L),maxy=min(400,j+L);
  20.                         int cnt=0;
  21.                         for (int k=minx;k<=maxx;k++)
  22.                             for (int l=miny;l<=maxy;l++)
  23.                                 if (map[k][l]&&dis(i,j,k,l)<=L)
  24.                                     cnt++;
  25.                         ans=max(ans,cnt);
  26.                 }
  27.         }
  28.         printf("%d\n",ans);
  29.     //fclose(stdin);
  30.     //fclose(stdout);
  31.         return 0;
  32. }
复制代码


本质为曼哈顿距离，故不必进行400^4的枚举
回复

使用道具 举报

魏晟伦

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
 楼主| 发表于 2021-10-22 16:28:03 | 显示全部楼层
T3
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define NUM (int)2e6+1
  4. #define EDGE (int)1e6+1
  5. #define POINT (int)1e5+1
  6. #define hash hashh
  7. #define map mapp
  8. using namespace std;
  9. int N,T,E;
  10. int x,f,u,v,l;
  11. int cnt,root,head[POINT],father[POINT];
  12. int mapcnt,map[NUM];
  13. int dp[POINT],res=1e18,resx;
  14. struct edge{
  15.         int to,len,next;
  16. }e[EDGE];
  17. inline int hash(int p){
  18.         return map[p]?map[p]:(map[p]=++mapcnt);
  19. }
  20. inline void link(int u,int v,int w){
  21.         cnt++;
  22.         e[cnt].next=head[u],e[cnt].len=w,e[cnt].to=v;
  23.         head[u]=cnt;
  24. }
  25. inline bool relax(int u,int v,int w){
  26.         if (dp[v]>dp[u]+w){
  27.                 dp[v]=dp[u]+w;
  28.                 return true;
  29.         }
  30.         return false;
  31. }
  32. void dfs(int p){
  33.         for (int i=head[p];i;i=e[i].next)
  34.             if (relax(p,e[i].to,e[i].len))
  35.                 dfs(e[i].to);
  36. }
  37. signed main(){
  38.     //freopen("river.in","r",stdin);
  39.     //freopen("river.out","w",stdout);
  40.         scanf("%lld%lld%lld",&N,&T,&E);
  41.         for (int i=1;i<N;i++){
  42.                 scanf("%lld%lld%lld",&x,&f,&l);
  43.                 link(hash(f),hash(x),l);
  44.                 father[hash(x)]=hash(f);
  45.         }
  46.        
  47.         int pos=hash(f);
  48.         while (father[pos])
  49.                 pos=father[pos];
  50.         root=pos;
  51.        
  52.         memset(dp,0x3f,sizeof(dp));
  53.         dp[root]=0;
  54.         dfs(root);
  55.        
  56.         E=hash(E);
  57.         for (int i=1;i<=T;i++){
  58.                 scanf("%lld%lld%lld",&u,&v,&l);
  59.                 u=hash(u),v=hash(v);
  60.                 link(u,v,l);
  61.                 if (relax(u,v,l))
  62.                     dfs(v);
  63.                 if (res>i*i+dp[E])
  64.                     res=i*i+dp[E],resx=i;
  65.         }
  66.        
  67.         if (res==1e18) res=-1;
  68.         printf("%lld\n%lld",resx,res);
  69.     //fclose(stdin);
  70.     //fclose(stdout);
  71.         return 0;
  72. }
复制代码
回复

使用道具 举报

魏晟伦

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
 楼主| 发表于 2021-10-22 16:31:29 | 显示全部楼层
T4
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define MOD 10000007
  4. #define N 50
  5. #define maxx 500000
  6. using namespace std;
  7. int Q,b,k;
  8. int cnt,q[N],v[N];
  9. int cntx,pri[10005];
  10. int ans,l,r,add[10005],mul[10005];
  11. bool vis[maxx+5];
  12. bool have[maxx];
  13. inline void get(){
  14.     for (int i=2;i<=maxx;i++){
  15.         if (cntx>10005)
  16.             break;
  17.         if (vis[i])
  18.             continue;
  19.         pri[++cntx]=i;
  20.         for (int j=i<<1;j<=maxx;j+=i)
  21.             vis[j]=true;
  22.     }
  23.     return;
  24. }
  25. signed main(){
  26.     //freopen("counter.in","r",stdin);
  27.     //freopen("counter.out","w",stdout);
  28.     scanf("%lld",&Q);
  29.     get();
  30.     while (Q--){
  31.         scanf("%lld%lld",&b,&k);
  32.         ans=0;
  33.         if (b==0){
  34.             printf("No way\n");
  35.             continue;
  36.         }
  37.         if (b==1){
  38.             for (int i=1;i<=k;i++)
  39.             ans^=((b%MOD)*pri[i])%MOD;
  40.             printf("%lld\n",ans);
  41.             continue;
  42.         }
  43.         cnt=0;
  44.         const int g=sqrt(b),mem=b;
  45.         memset(have,0,sizeof(have));
  46.         memset(add,0,sizeof(add));
  47.         for (int i=2;i<=g;i++){
  48.             if (b%i)
  49.                 continue;
  50.             have[i]=true,q[++cnt]=i;
  51.             v[cnt]=0;
  52.             while (!(b%i))
  53.                 b/=i,v[cnt]++;
  54.         }
  55.         if (b>1)
  56.             q[++cnt]=b,have[b]=true,v[cnt]=1;
  57.         for (int i=1;i<=cnt;i++){
  58.             int tmp=1;
  59.             for (int j=1;j<=v[i]+1;j++)
  60.             {
  61.                 tmp*=q[i];
  62.                 if (tmp>pri[10000]){
  63.                     tmp=0;
  64.                     break;
  65.                 }
  66.             }
  67.             if (!tmp)
  68.                 continue;
  69.             add[i]=tmp;
  70.         }
  71.         int thing=1,another=1;
  72.         for (int i=1;i<=k;i++){
  73.             while (another<=cnt&&(!add[another]))
  74.                 another++;
  75.             if (another<=cnt&&pri[thing]>add[another])
  76.                 mul[i]=add[another],another++;
  77.             else if (!have[pri[thing]])
  78.                 mul[i]=pri[thing],thing++;
  79.             else
  80.                 thing++,i--;
  81.             //cout<<"debug:"<<i<<' '<<mul[i]<<endl;
  82.             mul[i]%=MOD;
  83.         }
  84.         for (int i=1;i<=k;i++)
  85.             ans^=((mem%MOD)*mul[i])%MOD;
  86.         printf("%lld\n",ans);
  87.     }
  88.     //fclose(stdin);
  89.     //fclose(stdout);
  90.     return 0;
  91. }
复制代码

O(Q * ( k+sqrt(b) ) )
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

津ICP备19006949号-1 | 津公网安备12010102000465号

快速回复 返回顶部 返回列表