近几年ACM/ICPC区域赛铜牌题(1) [Cloned]
A-String
B-Little Tiger vs. Deep Monkey
C-Hard Code
题意：
给你一个字符串，n，m，输出n行，每行m个字符（字符串分割）。
#include<bits/stdc++.h>
using namespace std;
int t;
string s;
int n,m;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
cin>>s;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
printf("%c",s[i*m+j]);
}
printf("\n");
}
}
return 0;
}
D-Wall Painting
题意：
给了n个包，第k天混合任意k个包，得到 （ k n ） （^n_k） （kn）种不同方案，包混合后的值为混合的k个包的异或和，第k天的所有方案的异或和求和
solution：
将包的值进行二进制分解，由异或和性质可知相同为0，相异为1，当前二进制为如果要对答案产生贡献，那么当前二进制所选取1的个数必须为奇数，0的个数为剩余数量，两者之和必须大于等于k，直接进行组合数求解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const ll mo=1e6+3;
ll C(ll n,ll m){
static ll M=0,inv[10005],mul[10005],invMul[10005];
while(M<=n){
if(M){
inv[M]=M==1?1:(mo-mo/M)*inv[mo%M]%mo;
mul[M]=mul[M-1]*M%mo;
invMul[M]=invMul[M-1]*inv[M]%mo;
}
else mul[M]=1,invMul[M]=1;
M++;
}
return mul[n]*invMul[m]%mo*invMul[n-m]%mo;
}
int n;
ll a[1005];
int x[70];
ll res[1005];
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
res[i]=0;
}
memset(x,0,sizeof(x));
int cnt=0;
while(true)
{
bool flag=true;
for(int i=1;i<=n;i++)
{
if(a[i]%2==1)
x[cnt]++;
a[i]/=2;
if(a[i])flag=false;
}
if(flag)break;
cnt++;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=cnt;j++)
{
ll add=(1ll<<j)%mo;
for(int k=1;k<=i;k+=2)
{
if(x[j]<k||n-x[j]<i-k)continue;
res[i]=(res[i]+1ll*add*C(x[j],k)%mo*C(n-x[j],i-k)%mo)%mo;
}
}
}
printf("%lld",res[1]);
for(int i=2;i<=n;i++)
printf(" %lld",res[i]);
printf("\n");
}
return 0;
}
E-Ball
F-Zhuge Liang’s Password
题意：
给了两张n行n列的卡片，对其中一张卡片进行0，90，180，270度旋转，两张卡片重叠后，相同的地方最多有几处
solution：
暴力模拟。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n;
int a[35][35],b[35][35];
void zhuan()
{
int tem[35][35];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
tem[i][j]=a[n-j-1][i];
}
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j]=tem[i][j];
}
int main()
{
while(~scanf("%d",&n))
{
if(n==0)break;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&b[i][j]);
zhuan();
int res=0;
for(int i=0;i<4;i++)
{
if(i!=0)
zhuan();
int cnt=0;
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
if(a[j][k]==b[j][k])cnt++;
}
res=max(res,cnt);
}
printf("%d\n",res);
}
return 0;
}
G-Stealing Harry Potter’s Precious
题意：
给了一个n，m的二维矩阵，@为起点，要通过给定的k个点，问通过这k个点的最小距离。不能完全通过输出-1。（#不能走，.可以走）
solution：
将起点和给定的k个点都求以该点为起点到其他地方的最短距离。之后跑一边dfs，求不同的顺序下最短距离是多少。
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n,m,k;
int sx[10],sy[10];
char tu[105][105];
int d[10][105][105];
int dx[]={
0,0,1,-1},dy[]={
1,-1,0,0};
int vis[10];
int minn;
void bfs()
{
memset(d,INF,sizeof(d));
for(int i=0;i<=k;i++)
{
queue<P> que;
d[i][sx[i]][sy[i]]=0;
que.push(P(sx[i],sy[i]));
while(!que.empty())
{
P p=que.front();que.pop();
for(int j=0;j<4;j++)
{
int x=p.first+dx[j],y=p.second+dy[j];
if(x<1||x>n||y<1||y>m)continue;
if(tu[x][y]=='#'||d[i][x][y]!=INF)continue;
d[i][x][y]=d[i][p.first][p.second]+1;
que.push(P(x,y));
}
}
}
}
void dfs(int fa,int s,int c)
{
if(c==k){
minn=min(minn,s);
return;
}
for(int i=0;i<=k;i++)
{
if(vis[i]||d[fa][sx[i]][sy[i]]==INF)continue;
vis[i]=1;
dfs(i,s+d[fa][sx[i]][sy[i]],c+1);
vis[i]=0;
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0)break;
for(int i=1;i<=n;i++)
cin>>tu[i]+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(tu[i][j]=='@')
sx[0]=i,sy[0]=j;
}
}
scanf("%d",&k);
minn=INF;
for(int i=1;i<=k;i++)
scanf("%d%d",&sx[i],&sy[i]);
bfs();
memset(vis,0,sizeof(vis));
vis[0]=1;
dfs(0,0,0);
if(minn==INF)
printf("-1\n");
else
printf("%d\n",minn);
}
return 0;
}
H-Lights Against Dudely
I-Fibonacci Tree
J-Little Zu Chongzhi’s Triangles
K-How Many Maos Does the Guanxi Worth
L-GTY’s gay friends
M-The E-pang Palace
N-Dire Wolf
O-Happy Matt Friends
P-Intersection
Q-K.Bro Sorting
题意：
给了一个数组，问要进行多少伦冒泡排序
solution：
判断当前数是否比后面的某个数大就可以了。
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int t,n,a[1000005];
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
scanf("%d",&n);
for(int j=0;j<n;j++)
scanf("%d",&a[j]);
int ans=0,minn=INF;
for(int j=n-1;j>=0;j--)
{
if(a[j]>minn)ans++;
minn=min(minn,a[j]);
}
printf("Case #%d: %d\n",i,ans);
}
return 0;
}
R-A Curious Matt
题意：
给了n个位置，以及走到当前位置时的时间，求最大速度。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
struct node
{
int t,x;
bool operator <(node b)
{
return t<b.t;
}
}a[10010];
int main(){
int t;scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].t,&a[i].x);
sort(a+1,a+1+n);
double ans=0;
for(int i=2;i<=n;i++)
{
ans=max(ans,abs(a[i].x-a[i-1].x)*1.0/(a[i].t-a[i-1].t));
}
printf("Case #%d: %.2f\n",cas,ans);
}
return 0;
}
字节跳动公司氛围 552人发布