10.3 Morning
Problem A. problem
【题目描述】
【输入描述】
第一行三个数n, m, k，代表棋盘的行数、列数和小葱的个数。
接下来k行每行三个数x[i], y[i], d[i], f[i]，表示每个小葱一开始所在的行、列、面朝的方向以及战斗力。其中d[i]只可能是0,1,2,3中的一个，分别代表上下左右四个方 向。
最后一行一个整数t，代表结束的时刻。
【输出描述】
k行每行两个数，代表每棵小葱在时刻t的时候所在的位置。
【输入输出样例】
【input】
3 3 3
1 1 1 1
2 2 2 2
3 3 3 3
4
【output】
2 1
2 3
3 1
【数据范围】
【代码实现】
20分代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1005
using namespace std;
int mx[4]={-1,1,0,0},my[4]={0,0,-1,1};
int t,n,m,k,num[N][N];
struct qq{
int f,d,x,y,dd;
}a[N];
bool check(int s){
int nx=a[s].x+mx[a[s].d],ny=a[s].y+my[a[s].d];
if(nx==0||ny==0||nx==n+1||ny==m+1)return 1;
return 0;
}
int main(){
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++){
scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].d,&a[i].f);
num[a[i].x][a[i].y]=a[i].f;
}
scanf("%d",&t);
while(t--){
for(int i=1;i<=k;i++){//clear
if(a[i].dd)continue;
num[a[i].x][a[i].y]=0;
}
for(int i=1;i<=k;i++){//move
if(a[i].dd)continue;
if(check(i))a[i].d^=1;
else {
a[i].x+=mx[a[i].d],a[i].y+=my[a[i].d];
num[a[i].x][a[i].y]=max(num[a[i].x][a[i].y],a[i].f);
}
}
for(int i=1;i<=k;i++)if(a[i].dd==0&&num[a[i].x][a[i].y]>a[i].f)a[i].dd=1;//fight
}
for(int i=1;i<=k;i++)printf("%d %d\n",a[i].x,a[i].y);
return 0;
}40分代码
#include <cstdio>
#include <vector>
using namespace std;
int G[202][202][5];
int N,M,K,T;
int d[1001],x[1001],y[1001],f[1001],dead[1001];
int main () {
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
scanf("%d%d%d",&N,&M,&K);
for(int i=1;i<=K;i++) {
scanf("%d%d%d%d",&x[i],&y[i],&d[i],&f[i]);
G[x[i]][y[i]][++G[x[i]][y[i]][0]]=i;
}
scanf("%d",&T);
for(int t=1;t<=T;t++) {
for(int i=1;i<=K;i++) {
if(dead[i])
continue;
if(d[i]==0) {
if(x[i]-1<1) {
d[i]=1;
continue;
}
G[x[i]][y[i]][G[x[i]][y[i]][0]--]=0;
x[i]--;
G[x[i]][y[i]][++G[x[i]][y[i]][0]]=i;
}
if(d[i]==1) {
if(x[i]+1>N) {
d[i]=0;
continue;
}
G[x[i]][y[i]][G[x[i]][y[i]][0]--]=0;
x[i]++;
G[x[i]][y[i]][++G[x[i]][y[i]][0]]=i;
}
if(d[i]==2) {
if(y[i]-1<1) {
d[i]=3;
continue;
}
G[x[i]][y[i]][G[x[i]][y[i]][0]--]=0;
y[i]--;
G[x[i]][y[i]][++G[x[i]][y[i]][0]]=i;
}
if(d[i]==3) {
if(y[i]+1>M) {
d[i]=2;
continue;
}
G[x[i]][y[i]][G[x[i]][y[i]][0]--]=0;
y[i]++;
G[x[i]][y[i]][++G[x[i]][y[i]][0]]=i;
}
}
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
if(G[i][j][0]>1) {
int Max=0,alive=0;
for(int k=1;k<=G[i][j][0];k++)
if(f[G[i][j][k]]>Max)
Max=f[G[i][j][k]],alive=G[i][j][k];
for(int k=1;k<=G[i][j][0];k++)
if(G[i][j][k]!=alive)
dead[G[i][j][k]]=1;
for(int k=1;k<=G[i][j][0];k++)
G[i][j][k]=0;
G[i][j][0]=1;
G[i][j][1]=alive;
}
}
for(int i=1;i<=K;i++)
printf("%d %d\n",x[i],y[i]);
return 0;
}爆零的std（100分代码）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
const int maxk=1010;
int n,m,k,x[maxk],y[maxk],d[maxk],f[maxk],z[maxk],t;
bool alive[maxk];
int dx[4],dy[4];
void move(int p)
{
x[p] += dx[d[p]];
y[p] += dy[d[p]];
if (x[p]<1 || x[p]>n || y[p]<1 || y[p]>m)
{
x[p] -= dx[d[p]];
y[p] -= dy[d[p]];
d[p] ^= 1;
}
}
bool cmp(int a,int b)
{
if (x[a]!=x[b]) return x[a]<x[b];
else return y[a]<y[b];
}
int main()
{
dx[0]=-1;dx[1]=1;dy[2]=-1;dy[3]=1;
scanf("%d%d%d",&n,&m,&k);
for (int a=1;a<=k;a++)
scanf("%d%d%d%d",&x[a],&y[a],&d[a],&f[a]);
for (int a=1;a<=k;a++)
{
alive[a]=true;
z[a]=a;
}
scanf("%d",&t);
for (;t--;)
{
for (int a=1;a<=k;a++)
if (alive[a]) move(a);
sort(z+1,z+k+1,cmp);
for (int a=1;a<=k;)
{
int b=a,p=-1;
while (x[z[b]]==x[z[a]] && y[z[b]]==y[z[a]] && b<=k)
{
if (alive[z[b]] && (p==-1 || f[z[b]]>f[z[p]])) p=b;
b++;
}
for (int c=a;c<b;c++)
if (p!=-1 && c!=p) alive[z[c]]=false;
a=b;
}
}
for (int a=1;a<=k;a++)
printf("%d %d\n",x[a],y[a]);
return 0;
}Problem B. too
【题目描述】
【输入描述】
第一行两个整数N, M代表数的个数和规则数量。 接下来每行一个字符和一个整数t, n代表一条规则。
【输出描述】
输出一行一个整数，代表答案对12345取模之后的结果。
【输入输出样例】
【input】
5 2
a 1
b 2
【output】
16
方案包括： aaaaa, aaabb, aabab, aabba, abaab, ababa, abbaa, baaab, baaba, babaa, bbaaa, abbbb, babbb, bbabb, bbbab, bbbba。
【数据范围】
【代码实现】
20分代码
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define R register
#define ll long long
using namespace std;
const int mod = 12345;
int n, m, c[600][600], rule[100];
inline void read(int &x)
{
x = 0;
char ch = getchar();
while(!isdigit(ch))
{
ch = getchar();
}
while(isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return;
}
void work1()
{
c[0][0] = 1;
for(R int i = 1; i <= n; ++i)
{
c[i][0] = 1;
for(R int j = 1; j <= i; ++j)
{
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
for(R int i = 1; i <= m; ++i)
{
char ch;
cin >> ch, read(rule[i]);
}
int ans = 0;
for(R int i = 0; i * rule[1] <= n; ++i)
{
for(R int j = 0; j * rule[2] + i * rule[1] <= n; ++j)
{
if((n - j * rule[2] + i * rule[1]) % rule[3])
{
continue;
}
ans = (ans + c[n][i * rule[1]] * c[n - i * rule[1]][j * rule[2]]) % mod;
}
}
cout << ans;
return;
}
int main()
{
srand(19260817);
freopen("too.in", "r", stdin);
freopen("too.out", "w", stdout);
read(n), read(m);
if(n <= 25)
{
work1();
return 0;
}
cout << (rand() * rand()) % 12345;
return 0;
}60分代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200
#define mod 12345
#define LL long long
using namespace std;
int num[N][N],tt,sum,now[N];
int X[N],f[N],ans[N][N],sss[N][N],tmp[N][N];
LL n;int m;
char c[N];int a[N];
int gcd(int x,int y){
if(!y)return x;
return gcd(y,x%y);
}
void mul(int op){
memset(sss,0,sizeof(sss));
if(op==1){
for(int i=1;i<=tt;i++)
for(int j=1;j<=tt;j++)
for(int k=1;k<=tt;k++)
sss[i][j]=(sss[i][j]+ans[i][k]*tmp[k][j])%mod;
for(int i=1;i<=tt;i++)
for(int j=1;j<=tt;j++)ans[i][j]=sss[i][j];
}
else{
for(int i=1;i<=tt;i++)
for(int j=1;j<=tt;j++)
for(int k=1;k<=tt;k++)
sss[i][j]=(sss[i][j]+tmp[i][k]*tmp[k][j])%mod;
for(int i=1;i<=tt;i++)
for(int j=1;j<=tt;j++)tmp[i][j]=sss[i][j];
}
}
void qpow(){
while(n){
if(n&1)mul(1);
mul(2);n>>=1;
}
for(int i=1;i<=tt;i++)
for(int j=1;j<=tt;j++)
f[i]=(f[i]+ans[i][j]*X[j])%mod;
}
bool df(int s1,int s2){
int z=0;
for(int i=0;i<55;i++)
if(num[s1][i]!=num[s2][i])z++;
if(z>=2)return 0;
for(int i=0;i<55;i++)
if(num[s1][i]!=num[s2][i])
if(num[s2][i]-num[s1][i]==1||(num[s1][i]==a[i]-1&&num[s2][i]==0))return 1;
return 0;
}
void prework(){
X[1]=1;
for(int i=1;i<=tt;i++)ans[i][i]=1;
for(int i=1;i<=tt;i++){
for(int j=1;j<=tt;j++){
if(i==j)tmp[i][j]=sum;
if(df(i,j))tmp[i][j]=1;
}
}
}
void dfs(int x){
if(x==55){
tt++;
for(int i=0;i<55;i++)num[tt][i]=now[i];
return;
}
if(a[x]==0)dfs(x+1);
for(int i=0;i<a[x];i++)now[x]=i,dfs(x+1);
}
int main(){
freopen("too.in","r",stdin);
freopen("too.out","w",stdout);
cin>>n>>m;
for(int i=1,x;i<=m;i++){
cin>>c[i]>>x;int ss;
if(c[i]>='a')ss=c[i]-'a'+26;
else ss=c[i]-'A';
if(a[ss])a[ss]=a[ss]*x/gcd(a[ss],x);
else a[ss]=x;
}
for(int i=0;i<55;i++)if(a[i]==1)sum++;
dfs(0); prework(); qpow();
printf("%d",f[1]);
return 0;
}
爆零的std（100分代码）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<map>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#define inc(a,b) {a+=b;if (a>=mo) a-=mo;}
const int mo=12345;
int s,cnt,num,multi[30],c,pos[30];
long long n;
char st[3];
vector<int> status[125],nowway,v[30];
map< vector <int> , int > id;
int m1[125][125],m2[125][125],m3[125][125];
void dfs(int now)
{
if (now==cnt)
{
num++;
status[num]=nowway;
id[nowway]=num;
}
else
{
for (int a=0;a<multi[now];a++)
{
nowway.push_back(a);
dfs(now+1);
nowway.pop_back();
}
}
}
int gcd(int a,int b)
{
if (a % b==0) return b;
else return gcd(b,a % b);
}
int main()
{
cin>>n;
scanf("%d",&c);
for (int a=1;a<=c;a++)
{
scanf("%s",st);
int nowv;
scanf("%d",&nowv);
v[st[0]-'A'+1].push_back(nowv);
}
s=1;
for (int a=1;a<=26;a++)
if (v[a].size())
{
sort(v[a].begin(),v[a].end());
v[a].resize(unique(v[a].begin(),v[a].end())-v[a].begin());
int size=0;
for (int b=0;b<(int)v[a].size();b++)
{
bool able=true;
for (int c=0;c<b;c++)
if (v[a][b]%v[a][c]==0) able=false;
if (able)
{
v[a][size]=v[a][b];
size++;
}
}
v[a].resize(size);
if (v[a].back()==1) continue;
int lcm=1;
for (int b=0;b<(int)v[a].size();b++)
lcm=lcm*v[a][b]/gcd(v[a][b],lcm);
s*=lcm;
multi[cnt]=lcm;
pos[a]=cnt;
cnt++;
}
dfs(0);
for (int a=1;a<=num;a++)
{
nowway=status[a];
for (int b=1;b<=26;b++)
if (v[b].size())
{
if (v[b].back()==1) m1[a][a]++;
else
{
nowway[pos[b]]++;
nowway[pos[b]]%=multi[pos[b]];
int idx=id[nowway];
m1[a][idx]++;
nowway[pos[b]]+=multi[pos[b]]-1;
nowway[pos[b]]%=multi[pos[b]];
}
}
}
m2[1][1]=1;
while (n)
{
if (n&1)
{
memset(m3,0,sizeof(m3));
for (int a=1;a<=s;a++)
for (int b=1;b<=s;b++)
for (int c=1;c<=s;c++)
inc(m3[a][c],m2[a][b]*m1[b][c]%mo);
for (int a=1;a<=s;a++)
for (int b=1;b<=s;b++)
m2[a][b]=m3[a][b];
}
memset(m3,0,sizeof(m3));
for (int a=1;a<=s;a++)
for (int b=1;b<=s;b++)
for (int c=1;c<=s;c++)
inc(m3[a][c],m1[a][b]*m1[b][c]%mo);
for (int a=1;a<=s;a++)
for (int b=1;b<=s;b++)
m1[a][b]=m3[a][b];
n>>=1;
}
int ans=0;
for (int a=1;a<=num;a++)
{
nowway=status[a];
bool able=true;
for (int b=1;b<=26;b++)
if (v[b].size())
{
if (v[b].back()==1) continue;
bool fail=true;
for (int c=0;c<(int)v[b].size();c++)
if (nowway[pos[b]]%v[b][c]==0)
{
fail=false;
break;
}
if (fail)
{
able=false;
break;
}
}
if (able) ans=(ans+m2[1][a])%mo;
}
printf("%d\n",ans);
return 0;
}
Problem C. easy
【题目描述】
【输入格式】
第一行一个整数n，表示点的个数。 接下来一行n个整数，第i个整数表示第i个点的点权Ai。
【输出格式】
第一行输出为了获得点愉悦程度需要的最少花费。
接下来n行,第i行输岀0,1,2中的某一个数,输出0表示不买这一类糖果,输出1表示买小糖果,输出2表示买大糖果。如果有多种最优方案,输出其中一种即可。
【输入输出样例】
一行一个整数表示答案对991127取模的结果。
【input】
3
1 3 2
【output】
1
【数据范围】
【代码实现】
15分代码
#include<iostream>
#include<cstdio>
using namespace std;
const int mod = 991127;
int n,a[100005],ans;
struct edge{
int node,next,data;
}e[200005];
int tot,head[10005];
int num(int x)
{
int res=0;
while(x)
{
if(x&1) res++;
x>>=1;
}
return res;
}
void add(int x,int y,int z)
{
e[++tot].next =head[x];
e[tot].node=y;
e[tot].data =z;
head[x]=tot;
}
void dfs(int u,int ansp)
{
ansp=ansp%mod;
if(u==n)
{
ans+=ansp;
ans=ans%mod;
return;
}
for(int i=head[u];i;i=e[i].next )
{
int tmp=ansp;
ansp*=e[i].data ;
dfs(e[i].node,ansp);
ansp=tmp;
}
}
int main()
{
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
int t=num(a[i]&a[j]);
if(t>0)
add(i,j,t);
}
dfs(1,1);
printf("%d\n",ans);
return 0;
}30分代码
#include<iostream>
#include<cstdio>
#define rint register int
#define ull unsigned long long
using namespace std;
const int mod=991127;
const int maxn=1050;
struct edge{
ull to;
ull w;
edge* next;
edge(int to,int w,edge* next) {this->to=to;this->w=w;this->next=next;}
};
edge* head[maxn];
ull f[maxn];
ull val[maxn];
ull counts(int x){
int ans=0;
while(x)
ans+=(x&1),x>>=1;
return ans;
}
int main(){
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
ios::sync_with_stdio(false);
ull n;cin>>n;
for(rint i=1;i<=n;++i)
cin>>val[i];
for(rint i=1;i<=n;++i)
for(rint j=i+1;j<=n;++j){
if(val[i]&val[j]==0)
continue;
head[i]=new edge(j,counts(val[i]&val[j]),head[i]);
}
f[1]=1;
for(rint i=1;i<=n;++i)
for(edge* e=head[i];e;e=e->next)
f[e->to]=(f[e->to] + f[i] * e->w)%mod;
cout<<f[n];
return 0;
}爆零的std（100分代码）
#include<bits/stdc++.h>
#define MOD 991127
using namespace std;
int n;
const int MAXN=200010;
int a[MAXN],f[30],dp[MAXN];
inline void update(int &a,int b){
a+=b;
if(a>=MOD)a-=MOD;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(f,0,sizeof(f));
for(int i=0;i<30;i++)
if((a[1]>>i)&1) f[i]=1;
dp[1]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<30;j++)
if((a[i]>>j)&1)update(dp[i],f[j]);
for(int j=0;j<30;j++)
if((a[i]>>j)&1)update(f[j],dp[i]);
}
printf("%d\n",dp[n]);
return 0;
}