I题 Jigsaw
由题意可知,Corner pieces(c)只能为4个,Edge pieces(e)和Center pieces(m)与w,h相关。
推出式子可知为e=2×(w+h-4),m=(w-2)*(h-2),w×h=e+m+4,根据数据大小直接暴力找因子就好了。
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false)
typedef long long ll;
void solve()
{
ll c,e,m;
ll w,h;
cin>>c>>e>>m;
if(c==4)//必须为4个角
{
ll tmp=e+m+4;//w*h=e+m+4
for(int i=2;i*i<=tmp;i++){
if(tmp%i==0){//找因子
ll w=i,h=tmp/i;
if(e==(2*w+2*h-8)&&m==(w-2)*(h-2)){//满足条件
if(h>w) swap(w,h);//大的在前
cout<<w<<" "<<h<<endl;
return ;
}
}
}
}
cout<<"impossible"<<endl;
}
signed main()
{
ios;
cin.tie(0);
// cin>>t;
//while(t--)
{
solve();
}
return 0;
}
C Corrupted Contest
已知给出的是有效的榜单,那么只有唯一的做题数和不唯一做题数。
唯一就是(除全为0的情况)从第一名开始到最后一名有罚时数的参赛队伍,做题数是从m
1的 如果没有1 那就说明是不唯一的情况。
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define ios ios::sync_with_stdio(false)
typedef long long ll;
map<int,int>mp;
void solve(){
int n,m;
cin>>n>>m;
vector<int>a(n),b(n);//罚时数,做题数
int t=m;
for(int i=0;i<n;i++){
cin>>a[i];
if(i==0&&a[i]!=0)b[i]=t,mp[t]++;//第一名罚时不为0
else if(i==0&&a[i]==0)b[i]=0,mp[0]++;
if(i!=0&&a[i]>=a[i-1]){//设置为做题数相同
b[i]=b[i-1];
mp[b[i]]++;
}
else if(i!=0&&a[i]<a[i-1]){//做题数不同
if(a[i]){//不为0的情况
b[i]=b[i-1]-1;
mp[b[i]]++;
}else {//为0的情况
b[i]=0;
mp[0]++;
}
}
}
if(mp[1]==0&&mp[0]!=n)//罚时数 不全为0 且没有做了1题的 则不确定
cout<<"ambiguous"<<endl;
else
for(int i=0;i<n;i++)
cout<<b[i]<<endl;
}
signed main()
{
ios;
cin.tie(0);
{
solve();
}
return 0;
}
D Efficiently Elevated
从最高楼层开始搜索,只入队楼层小于等于它的,这一部分只会用一部电梯,搜索几次就是几部电梯。
#include "iostream"
#include "cstring"
#include "algorithm"
#include "queue"
#define mem(n) memset(n,0,sizeof n)
using namespace std;
int map[502][502];
bool vis[502][502];
int d[4][2]={1,0,-1,0,0,1,0,-1},n,m;
struct node{
int x,y,val;
}t[250005];
bool cmp(node a,node b){
return a.val>b.val;
}
void bfs(int x,int y){
queue<node> q;
node node1;
node1.x=x,node1.y=y,node1.val=map[x][y];
q.push(node1);
vis[x][y]=1;
while(!q.empty()){
node node2=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx=node2.x+d[i][0];
int yy=node2.y+d[i][1];
//只入队 楼层小于等于当前阶段的
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&map[node2.x][node2.y]>=map[xx][yy]&&!vis[xx][yy]){
node node3;
node3.val=map[xx][yy],node3.x=xx,node3.y=yy;
q.push(node3);
vis[xx][yy]=1;
}
}
}
}
int main()
{
cin>>n>>m;
mem(map),mem(vis);
int cnt=0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cin>>map[i][j];
t[++cnt]={i,j,map[i][j]};
}
}
sort(t+1,t+cnt+1,cmp);
int re=0;
for(int i=1;i<=cnt;i++)
{
if(map[t[i].x][t[i].y]==0||map[t[i].x][t[i].y]==1) continue;
if(!vis[t[i].x][t[i].y])
{
re++;
bfs(t[i].x,t[i].y);
}
}
cout<<re<<endl;
return 0;
}
F题 Generator Grid
别人的思路
如果只考虑市与市之间的电线 可以用最小生成树解决 那么阻碍是市可以建发电站。
可以将某市建发电站 看作是0市与该市的电线,其他市是从1开始的,不会与0市相连(保证了至少有一个发电站),那么以此建立最小生成树即可解决问题。
别人的AC代码