2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest
C Evolution Game
题目链接
题意：有n个不同版本的野兽，定义属性：第 i 个野兽有 i 个眼睛和 h[i] 个角，你可以任意从中选择一个野兽进行进化，每次进化角数量必须增加，而且进化后假设有a 个眼睛 b个角，假设h[i]=b，那么abs(a-i)<=w，否则不能进化，求最多的进化次数。
思路：进化前向进化后建立单项边，跑标记的BFS
By sharp_cone, contest: 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest, problem: (C) Evolution Game, Accepted, #
#include <bits/stdc++.h>
#define maxn 5005
#define inf 0x3f3f3f3f
using namespace std;
int n,w;
int h[maxn];
int indeg[maxn];
int vis[maxn];
vector <int>G[maxn];
void input(){
scanf("%d%d",&n,&w);
for(int i=1;i<=n;i++){
// h[i]=i;
scanf("%d",&h[i]);
vis[i]=-1;
}
for(int i=1;i<=n;i++){
int temp=inf;
for(int j=1;j<=w;j++){
if(i+j>n)break;
if(h[i]<h[i+j]&&h[i+j]<=temp){
temp=h[i+j];
G[i].push_back(i+j);
indeg[i+j]++;
}
}
temp=inf;
for(int j=1;j<=w;j++){
if(i-j<1)break;
if(h[i]<h[i-j]&&h[i-j]<=temp){
temp=h[i-j];
G[i].push_back(i-j);
indeg[i-j]++;
}
}
}
// cout<<"!!!"<<endl;
}
struct node{
int index,step;
};
void solve(){
queue <node>q;
for(int i=1;i<=n;i++)
if(!indeg[i]){
q.push((node){i,0});
vis[i]=0;
}
int ans=0;
while(!q.empty()){
node f=q.front();
// cout<<f.index<<' '<<f.step<<endl;
ans=max(ans,f.step);
q.pop();
for(int i=0;i<G[f.index].size();i++){
int v=G[f.index][i];
if(vis[v]!=-1&&vis[v]==f.step+1)
continue;
vis[v]=f.step+1;
q.push((node){v,f.step+1});
}
}
printf("%d\n",ans);
}
int main(){
input();
solve();
}
D Bus Stop
题目链接
题意：有n个房子的坐标，你要建立公交车站，使得每个房子离最近的车站不过10公里，求最少的车站。
思路：贪心，在房子后10米建公交车站
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
int a[maxn];
int main() {
int m;
scanf("%d", &m);
while (m--) {
int n;
scanf("%d", &n);
if(n==0){
printf("0\n");
continue;
}
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
int cur = a[1] + 10;
int cnt = 1;
for (int i = 2; i <= n; i++) {
if (a[i] <= cur + 10)continue;
cnt++;
cur = a[i] + 10;
}
cout << cnt << endl;
}
}
/*
2
5
1 2 3 200 210
4
10 30 80 200
*/ E How Many Groups
G Communication
题目链接
题意：给一些有向边，如果两个点可以互达，那么这两个点属于同一组，求你给有向图分组。
思路：求强连通，搜索
#include <bits/stdc++.h>
#define maxn 505
using namespace std;
const int inf = 0x3f3f3f3f;
int a[maxn];
int g[maxn][maxn];
vector<int>v[maxn];
int vis[maxn];
void dfs(int x, int fa) {
for (int y : v[x]) {
if (!vis[y] && y != fa) {
vis[y] = 1;
dfs(y, x);
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int m;
scanf("%d", &m);
memset(g, 0, sizeof g);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
x++; y++;
g[x][y] = 1;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] |= g[i][k] & g[k][j];
}
}
}
for (int i = 1; i <= n; i++) {
v[i].clear();
vis[i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j] && g[j][i]) {
v[i].push_back(j);
v[j].push_back(i);
//cout << "i : j " << i << " " << j << endl;
}
}
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
//cout << "** " << i << endl;
vis[i] = 1;
cnt++;
dfs(i, -1);
}
}
printf("%d\n", cnt);
}
}
/*
3
6
2 0 5 5 0
5
7 0 1 0 2 1 0 1 3 2 4 3 1 4 2
3
4 0 1 0 2 1 0 1 2
*/ H As Rich as Crassus
题目链接
题意：给定三个余数和答案，求满足条件的被余数的开方
思路：扩展中国剩余定理，得到数，开3次方求能否存在，不能则+LCM。存在精度问题，则if aaa<res then a=a+1。可解决。
#include <bits/stdc++.h>
#define maxn 5
#define EPS 1e-10
typedef long long ll;
using namespace std;
ll bi[maxn], ai[maxn];
ll gcd(ll a, ll b) {
while (b ^= a ^=b^= a %= b);
return a;
}
ll lcm(ll a, ll b) {
return a * b / gcd(a, b);
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll gcd = exgcd(b, a%b, x, y);
ll tp = x;
x = y;
y = tp - a / b * y;
return gcd;
}
ll qmul(ll a, ll b, ll m) {
ll ans = 0;
ll k = a;
ll f = 1;
if (k<0) {
f = -1;
k *= -1;
}
if (b<0) {
f *= -1;
b *= -1;
}
while (b) {
if (b & 1)
ans = (ans + k) % m;
k = (k + k) % m;
b >>= 1;
}
return ans * f;
}
ll excrt() {
ll x, y, k;
ll M = bi[1], ans = ai[1];
for (int i = 2; i <= 3; i++) {
ll a = M, b = bi[i], c = (ai[i] - ans % b + b) % b;
ll gcd = exgcd(a, b, x, y);
ll bg = b / gcd;
if (c%gcd != 0)
return -1;
x = qmul(x, c / gcd, bg);
ans += x * M;
M *= bg;
ans = (ans%M + M) % M;
}
return (ans%M + M) % M;
}
void input() {
for (int i = 1; i <= 3; i++)
scanf("%lld", &bi[i]);
for (int i = 1; i <= 3; i++)
scanf("%lld", &ai[i]);
}
long double temp;
bool check(ll res){
temp=pow(res,1.0/3);
// cout<<temp<<endl;
return temp*temp*temp-1.0*res<EPS;
}
void solve() {
ll res = excrt();
ll LCM = lcm(lcm(bi[1], bi[2]), bi[3]);
while (!check(res)) {
res += LCM;
}
if(temp*temp*temp<res)
printf("%lld\n",(ll)temp+1);
else
printf("%lld\n",(ll)temp);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
input();
solve();
}
}
/*
2
6 11 19
5 4 11
25 36 7
16 0 6
*/ J Floating-Point Hazard
题目链接
题意：解给定的式子
思路：积分，待补
K The Stream of Corning 2
题目链接
题意：两种操作 1:l val r 表示在[l,r]时间内有val值，2:l k 求时间为l时，存在第k大值。
思路：优先队列维护右区间，主席树维护区间第k大
#include <bits/stdc++.h>
#define maxn 100005
#define maxN 1000005
using namespace std;
int n;
int opt,l,val,r;
struct node{
int l,r;
int cnt;
node(){
l=r=cnt=0;
}
}T[maxN*22];
int rt[maxn*2];
int tot=0;
void update(int &x,int y,int l,int r,int pos,int val){
T[++tot]=T[y];
T[tot].cnt+=val;
x=tot;
if(l==r)
return;
int mid=(l+r)>>1;
if(pos<=mid)
update(T[x].l,T[y].l,l,mid,pos,val);
else
update(T[x].r,T[y].r,mid+1,r,pos,val);
}
int query(int x,int y,int l,int r,int k){
if(l==r)
return l;
int mid=(l+r)>>1;
int sum=T[T[y].l].cnt-T[T[x].l].cnt;
if(k<=sum)
return query(T[x].l,T[y].l,l,mid,k);
else
return query(T[x].r,T[y].r,mid+1,r,k-sum);
}
void input(){
tot=0;
scanf("%d",&n);
priority_queue<pair<int,int> >q;
int now=1;
for(int i=1;i<=n;i++){
scanf("%d",&opt);
if(opt==1){
scanf("%d%d%d",&l,&val,&r);
update(rt[now],rt[now-1],1,maxN,val,1);
now++;
q.push(make_pair(-r,val));
}else{
scanf("%d%d",&l,&val);
while(!q.empty()&&-q.top().first<l){
update(rt[now],rt[now-1],1,maxN,q.top().second,-1);
now++;
q.pop();
}
int ans=query(rt[0],rt[now-1],1,maxN,val);
if(ans>1000000)
printf("-1\n");
else
printf("%d\n",ans);
}
}
}
int main(){
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
printf("Case %d:\n",cas );
input();
}
}
/*
1
10
1 1 10 7
1 2 9 4
2 4 1
1 5 2 6
2 6 2
2 7 2
1 8 2 20
1 9 1 15
1 10 3 13
2 11 3
*/ L Largest Allowed Area
题目链接
题意：求01矩阵中只有一个1的最大子矩阵
思路：nnlogn。二分+枚举+快读，卡过。正解是用单调队列。
#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int n,m;
int g[maxn][maxn];
int sum[maxn][maxn];
bool check(int x){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i+x-1>n||j+x-1>m)
break;
if(sum[i+x-1][j+x-1]+sum[i-1][j-1]-sum[i-1][j+x-1]-sum[i+x-1][j-1]==1){
// cout<<i<<" "<<j<<" "<<x<<endl;
return 1;
}
}
}
return 0;
}
int scan(){
int res=0,flag=0;
char ch;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+(ch-'0');
return flag?-res:res;
}
void input(){
n=scan();m=scan();
int r=min(n,m);
r++;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
g[i][j]=scan();
sum[i][j]=0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+g[i][j];
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// printf("%d ",sum[i][j]);
// }
// printf("\n");
// }
int l=0;
int ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
printf("%d\n",ans);
}
int main(){
int t;
t=scan();
while(t--){
input();
// solve();
}
}
/*
4 4
0 0 0 0
0 1 0 1
0 0 0 0
0 1 0 1
10 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
20 10
1 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
*/
京公网安备 11010502036488号