首页 > 代码库 > 【5.5考试】
【5.5考试】
三道题，几乎爆零，状态很不好，考到一半直接写数学作业去了。。
1.
时间限制：1s 空间限制：1M
Description
给出2n个正整数，有且只有两个数出现奇数次，从小到大输出这两个数。
Input
第一行给出一个n，第二行有2n个数。
Output
从小到大输出答案。
| Simple Input 1 | Simple Output 1 |
|---|---|
| 5 | 1 6 |
| 1 2 3 4 5 2 3 4 5 6 |
| Simple Input 2 | Simple Output 2 |
|---|---|
| 2 | 1 2 |
| 1 1 1 2 |
Hint
n<=100000 所有数字均不超过int且均为正整数
看起来就很难的样子。只有两个数出现了奇数次，自然想到xor，所有数xor，最后的xor值就是a^b的值。然后怎么判断a，b究竟是哪两个数？
1010110 对于前面这个数（记为sum），假如是两个数^而成，那么sum某位置是1（记此位置为pos），a，b中必有某一个数这一位为1，另一个数此位为0。
用sum去^所有pos位为1的数，得到的就是a，b其中一个数，另一个数用 sum^已得的数就好了。
还有一点，此题数据范围太大而空间太小（后来数据又加强了），不可能存下所有给出的数。所以必须预处理出某一位为1时所有此位为1的数异或出的值。
CODE：
1 #include<cstdio> 2 using namespace std; 3 int bit[32],sum,n; 4 int main(){ 5 freopen("one.in","r",stdin);freopen("one.out","w",stdout); 6 scanf("%d",&n);n*=2; 7 int x,a,b; 8 for(int i=1;i<=n;i++){ 9 scanf("%d",&x);sum^=x;10 for(int j=0;j<32;j++)11 if((x>>j)&1)bit[j]^=x;12 }13 for(int i=0;i<32;i++){14 if(sum>>i&1){15 a=bit[i];16 b=sum^bit[i];17 }18 }19 if(a>b){int t=a;a=b;b=t;}20 printf("%d %d",a,b);21 return 0;22 }
2
时间：1s 空间：256M
| Simple Input 1 | Simple Output 1 |
|---|---|
| 5 1 1 0 | 1 |
| 0 |
| Simple Input 2 | Simple Output 2 |
|---|---|
| 10 19260817 7 3 | 2 |
| 1 3 5 7 9 |
Hint n<=1000000 此题有多种方案，任意输出一种即可
通过样例可以看出，后面的商品价格有点高。。
这么思考：可以购买连续的一段区间来达到目的。
那么只需要记录对n取模后的前缀和，如果某商品（标号记为to）的前缀和等于在它之前某商品（记为to）的前缀和，只需要购买from和to之间的商品就行。
这样购买一定有解。原因：算上0（一个都不买），共有n+1个前缀和，那么一定有2个前缀和相同，所以一定有解。
CODE：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define ll long long 7 #define inf 2147483647 8 #define N 10000005 9 using namespace std;10 int sum[N],vis[N],A,B,n,from,to;11 ll lt;12 int main(){13 freopen("rich.in","r",stdin);freopen("rich.out","w",stdout);14 scanf("%d%d%d%I64d",&n,&A,&B,<);15 if(lt==0){printf("1\n0");return 0;}16 for(int i=0;i<=n;i++)vis[i]=-1;17 sum[1]=lt%n;sum[0]=0;18 vis[sum[1]]=1;vis[0]=0;19 for(int i=2;i<=n;i++){20 lt=(1ll*A*lt+B)%n;21 sum[i]=(sum[i-1]+lt)%n;22 if(vis[sum[i]]>=0){23 from=vis[sum[i]]+1;24 to=i;break;25 }26 else vis[sum[i]]=i;27 }28 printf("%d\n",to-from+1);29 for(int i=from-1;i<=to-1;i++)printf("%d ",i);30 return 0;31 }
3
时间：1s 空间：256M
Description
给出一个的地图，然而只有一些地方有Wi-Fi，dp66为了看直播，只走有Wi-Fi的地方。
现在Ta想从左上角到右下角，问最少要移动多少Wi-Fi覆盖区域，使得Ta可以到终点。
Input
第一行有两个数，接下来是一个的地图，‘.‘表示空地，‘#‘表示有Wi-Fi覆盖。
Output
输出最少移动区域数，若无法这输出-1。
Simple Input 1
4 7#...####...#.###..#.#.#....#
Simple Output 1
3
Simple Input 2
4 5......###.####......
Simple Output 2
-1
Hint n<=m<=50
就是一个bfs，移动的wifi的个数=路径上走过的‘ . ‘的个数。
用最短路的思想优化，否则TLE。
优化：如果此前通过某种途径到达此点的所走过的‘ . ‘的个数比这条路径所走的‘ . ‘的个数少，那么此条路径不再向后拓展。道理很显然。
CODE：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<cmath> 7 #define ll long long 8 #define inf 2147483647 9 #define N 250510 using namespace std;11 int n,m,cnt,dp[55][55][N];12 int dx[]= {0,0,1,-1};13 int dy[]= {1,-1,0,0};14 15 char mp[55][55];16 struct node {17 int x,y,pit,wif;18 bool operator <(const node &a)const {19 return pit>a.pit;20 }21 };22 priority_queue<node>q;23 24 25 void solve()26 {27 node st;28 st.x=st.y=1;29 st.pit=(mp[1][1]==‘.‘);30 st.wif=(mp[1][1]==‘#‘);31 q.push(st);32 while(!q.empty()) {33 node u=q.top();34 q.pop();35 int x=u.x,y=u.y,wif=u.wif,pit=u.pit;36 if(x==n&&y==m) {37 printf("%d",pit);38 break;39 }40 node v;41 for(int i=0; i<4; i++) {42 v.x=x+dx[i];43 v.y=y+dy[i];44 if(v.x>n||v.x<1||v.y>m||v.y<1)continue;45 v.wif=u.wif+(mp[v.x][v.y]==‘#‘);46 v.pit=pit+(mp[v.x][v.y]==‘.‘);47 if(v.pit>=dp[v.x][v.y][v.pit])continue;//剪枝48 dp[v.x][v.y][v.pit]=v.pit;49 q.push(v);50 }51 }52 }53 54 int main()55 {56 freopen("way.in","r",stdin);57 freopen("way.out","w",stdout);58 scanf("%d%d",&n,&m);59 memset(dp,0x3f,sizeof(dp));60 for(int i=1; i<=n; i++) {61 scanf("%s",mp[i]+1);62 for(int j=1; j<=m; j++)63 if(mp[i][j]==‘#‘)cnt++;64 }65 if(cnt<n+m-1)printf("-1");66 else solve();67 return 0;68 }
【5.5考试】