首页 > 代码库 > 【68测试20161117】【数论】【乱搞】【前缀和】

【68测试20161117】【数论】【乱搞】【前缀和】

第一题:

  素数密度:给一个区间[L,R],求区间中的素数的个数。L、R<=214748367,L-R<=1000000

解:看到这么大的数据都有点慎得慌。首先,根据筛数法,这么大的数只需要筛sqrt(r)大的素数就可以了。把1~sqrt(r)的素数筛出来,然后用这些素数筛L~R的数。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define ll long long  6 #define maxn 1000005 7 #define N 20005 8 using namespace std; 9 int l,r,len,ans,pri[maxn],idx;10 bool vis[maxn],v[maxn];11 long long ti;12 void workk()13 {14     for (int i=2;i<=maxn;i++)//注意是maxn,不写i*i<=r是因为最后一次乘的时候可能会超int 15     if (!vis[i]){16         pri[++idx]=i;17         for (ll j=(ll)i*(ll)i;j<=maxn;j+=i)18         if (!vis[j]){19             vis[j]=true;20         }21     }22 }23 int main()24 {25     freopen("prime.in","r",stdin);26     freopen("prime.out","w",stdout);27     scanf("%d%d",&l,&r);28     workk();29     for (int i=1;i<=idx;i++)30     {31         int x=r/pri[i]*pri[i];//***找到离R最近的那个要筛掉的数 32         while (x>pri[i]&&x>=l)//> not >= 因为pri[i]为质数 33         {34             v[x-l]=true;x-=pri[i];35         }36     }37     for (int i=0;i<=r-l;i++)38      if (!v[i]) ans++;39     printf("%d",ans);40     return 0;41 }

第二题:

  从1~n的所有数的各个位的数字之和。即123=1+2+3=6.然后每个1~n的数的和。

解:一看就要找规律。按照位数来数这一位重复了多少1~9(∑=45)和余下的。再把每个位求的答案加起来。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #ifdef WIN32 6 #define AUTO "%I64d" 7 #else  8 #define AUTO "%lld" 9 #endif10 #define ll long long11 #define INF 1e912 using namespace std;13 ll n,f[15],ans;14 void pre()15 {16     f[1]=45;17     for (int i=2;i<=10;i++)18       f[i]=f[i-1]*10;19 }20 int main()21 {22     freopen("count.in","r",stdin);23     freopen("count.out","w",stdout);24     pre();25     scanf(AUTO,&n);26     ll x=1;27     int st=0;28     for (int i=0;i<10;i++){29         x*=10;30         if (x>n){31             st=i;32             break;33         } 34     }35     x/=10;36     while (st>=0)37     {38         ll cur=n/x;//当前位的数字 39         if (st==0) {40             cur=n%10;41             for(int i=1;i<=cur;i++) ans+=i;//单独处理个位    42         }43         else{44             ans+=cur*f[st];//这一位有多少整的1~9:如123中十位上重复了12次1~9 45             ll aa=cur%10;46             if (aa>1) {47                 for (int i=1;i<aa;i++)48                   ans+=x*i;//除了整的1~9还余了很多个,123十位上还应该有10个1 ,233百位上还有100个1,十位上还有10个1,2 49             }50             ll bb=n-cur*x;//123百位上还应该有23个1 ,十位上还应该有3+1个2 51             ans+=(bb+1)*aa;52         }53         x/=10;54         st--;55     }56     printf(AUTO,ans);57     return 0;58 }

第三题:

矩形
文件名:brother.pas/c/cpp
时限:1S
空间:256M
Description
  胜负胸中料已明,又从堂上出奇兵。秋实大哥是一个下棋好手,独孤求败的他觉得下棋已经无法满足他了,他开始研究一种新的玩法。
在一个n×m的棋盘上,放置了k个车,并且他在棋盘上标出了q个矩形,表示矩形内部是战略要地。
秋实大哥要求一个矩形内的每一个格子,都至少能被一辆在矩形内的车攻击到,那么这个矩形就是被完整保护的。
现在秋实大哥想知道每一个矩形是否被完整保护。
Input
  第一行包含四个整数n,m,k,q,表示棋盘的大小,车的数量以及矩形的数量。
  接来下k行,每行包含两个整数x,y,表示有一辆车位于从左往右第x列,从下往上第y行。
  接下来q行,每行包含四个整数x1,y1,x2,y2,表示一个矩形的左下角和右上角坐标。
  1≤n,m≤1e5,1≤k,q≤2e5,1≤x1≤x2≤1e5,1≤y1≤y2≤1e5,1≤x≤1e5,1≤y≤1e5。
Output
  输出q行,对于每一次询问,这个矩形若被完整保护了输出"YES",否则输出"NO"。
Sample input
  4 3 3 3
  1 1
  3 2
  2 3
  2 3 2 3
  2 1 3 3
  1 2 2 3
Sample Output
  YES
  YES
  NO
Limit
  此题无小数据


解:说好的没有小数据。我就没有写暴力。结果.....暴力60。车:象棋中的ju,只能走直线。

  暴力:每一行,每一列的前缀和。只要一个矩阵的所有列或者所有行都有至少一个车。O(q*(n+m))复杂度。

  注意:n为列数,m为行数。。。。。。

60分代码:

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 #define maxn 3005 7 #define N 100005 8 using namespace std; 9 int n,m,k,q,idx;10 int l[maxn][maxn],h[maxn][maxn];11 bool mp[maxn][maxn];12 int main()13 {14     freopen("brother.in","r",stdin);15     freopen("brother.out","w",stdout);16     scanf("%d%d%d%d",&n,&m,&k,&q);    17     for (int i=1;i<=k;i++)18     {19         int x,y;20         scanf("%d%d",&x,&y);21         //ju[i].xi=x;ju[i].yi=y;22         mp[x][y]=true;23     }24     for (int i=1;i<=n;i++)//lie25       for (int j=1;j<=m;j++)//hang26         {27             l[i][j]=l[i][j-1];28             h[i][j]=h[i-1][j];29             if (mp[i][j]) {30                 l[i][j]++;h[i][j]++;31             }32         }33     for (int i=1;i<=q;i++)34     {35         int xi,yi,xj,yj;36         scanf("%d%d%d%d",&xi,&yi,&xj,&yj);37         int ti=min(xi,xj),tj=max(xi,xj),tt=min(yi,yj),tv=max(yi,yj);38         bool hang=true,lie=true;39         for (int j=ti;j<=tj;j++)40           if (l[j][tv]-l[j][tt-1]==0) lie=false;41         for (int j=tt;j<=tv;j++)42           if (h[tj][j]-h[ti-1][j]==0) hang=false;43         if (lie||hang){44             printf("YES\n");45             continue;46         } 47         printf("NO\n");48     }49     return 0;50 }

 

【68测试20161117】【数论】【乱搞】【前缀和】