第一题 Grid
#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;
int n,m,res;
char mm[555][555];
int maze[555][555];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int vis[555][555];
int step;
struct node
{
int x,y;
int step;
};
void bfs()
{
node a;
a.x = 0;
a.y = 0;
a.step = 0;
queue<node>Q;
Q.push(a);
vis[0][0] = 1;
while(!Q.empty())
{
node tem = Q.front();
Q.pop();
if(tem.x == m-1 && tem.y == n-1)
{
printf("%d\n",tem.step);
return ;
}
else
{
for(int i=0;i<4;i++)
{
node tt;
tt.x = tem.x + dx[i] * maze[tem.x][tem.y];
tt.y = tem.y + dy[i] * maze[tem.x][tem.y];
if(tt.x>=0 && tt.x< m && tt.y >= 0 && tt.y <n && !vis[tt.x][tt.y])
{
tt.step = tem.step + 1;
vis[tt.x][tt.y] = 1;
Q.push(tt);
}
}
}
}
printf("-1\n");
return ;
}
int main()
{
while(cin>>m>>n)
{
clr(maze);
clr(vis);
for(int i=0;i<m;i++)
{
scanf("%s",mm[i]);
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
maze[i][j] = mm[i][j] - '0';
}
}
bfs();
}
return 0;
}
第二题 Summer Trip
#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;
int pre[1010];
int num[1010];
int vis[1010];
int tt[1010];
bool cmp(int a,int b)
{
return vis[a]<vis[b];
}
int Find(int x)
{
if(pre[x] == x) return x;
return pre[x] = Find(pre[x]);
}
void Union(int a,int b)
{
int A = Find(a);
int B = Find(b);
if(A!=B)
{
pre[B] = A;
}
}
int main()
{
int t,u,v,n,m,cas = 1;
cin>>t;
while(t--)
{
cin>>n>>m;
clr(num);
clr(vis);
clr(tt);
for(int i=1;i<=n;i++)
{
pre[i] = i;
}
for(int i=1;i<=n;i++)
{
cin>>num[i];
}
for(int j=1;j<=m;j++)
{
cin>>u>>v;
Union(u,v);
}
int pos = 0;
for(int i=1;i<=n;i++)
{
int xx = Find(i);
if(!vis[xx]) tt[pos++]=xx;
vis[xx]+=num[i];
}
sort(tt,tt+pos,cmp);
printf("Case %d: %d\n",cas++,pos);
for(int i=0;i<pos;i++)
{
if( i != pos - 1 ) printf("%d ",vis[tt[i]]);
else printf("%d\n",vis[tt[i]]);
}
}
return 0;
}
第三题 Matrices with XOR property
#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;
int vis[100010];
int maze[1010][1010];
int main()
{
int t , n , m ;
scanf("%d",&t);
while ( t-- )
{
int pos=0;
scanf("%d%d",&n,&m);
clr(vis);
for(int i = 1; i <= n; i++)
{
for ( int j = 1 ; j <= m ; j++)
{
maze[i][j] = i^j;
pos = max(pos,maze[i][j]);
vis[maze[i][j]]++;
}
}
ll ans = 1;
for(int i=0;i<=pos;i++){
if(vis[i] == 0) continue;
ll pro = 1;
for(int j=vis[i];j>=1;j--)
{
pro=(pro*j)%mod;
}
ans=(ans*pro)%mod;
}
printf("%lld\n",ans);
}
return 0;
}
第四题 Weird Rounding
#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;
int num[100];
int main()
{
ll n,k,pos=0;;
cin>>n>>k;
if(n == 0) {printf("0\n");return 0;}
int yy = n;
while(yy)
{
num[pos++]=yy%10;
yy/=10;
}
ll xx = 1;
for ( int i = 0 ; i < k ; i++ ){
xx *= 10;
}
if( xx > n )
{
printf("%d\n",pos-1);return 0;
}
else
{
int res=0;
int cnt=0;
for ( int i = 0 ; i < pos ; i++ )
{
if ( cnt == k ){ break; }
if ( num[i] ){ res++; }
if ( !num[i] ){ cnt++; }
}
if(cnt < k) printf("%d\n",pos-1);
else printf("%d\n",res);
}
return 0;
}
第五题 Dishonest Sellers
#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;
ll A[201010];
ll B[201010];
struct node
{
int val;
int id;
}ca[201010];
int vis[201010];
bool cmp(node a,node b)
{
return a.val < b.val;
}
int main()
{
int n , k ;
scanf("%d%d" , &n , &k);
memset(vis,0,sizeof(vis));
for ( int i = 0 ; i < n ; i++){
scanf ( "%I64d" , &A[i] );
}
for ( int j = 0 ; j < n ; j++){
scanf ( "%I64d" , &B[j] );
}
for ( int k = 0 ; k < n ; k++){
ca[k].val = A[k] - B[k];
ca[k].id = k;
}
sort(ca, ca + n , cmp);
/*for(int i = 1 ; i <= n ; i++)
{
cout <<"ca["<< i <<"] val : "<< ca[i].val <<" id : "<<ca[i].id<<endl;
cout << A[ca[i].id] << " " << B[ca[i].id] <<endl;
}*/
ll sum = 0;
for(int i = 0 ; i < n ; i++)
{
if(i > k - 1 && ca[i].val > 0) { break; }
sum += A[ca[i].id];
vis[ca[i].id]=1;
}
for(int j = 0 ; j < n ; j++)
{
if(!vis[ca[j].id])
sum += B[ca[j].id];
}
printf("%I64d\n",sum);
return 0;
}
网友评论