2019 ICPC Yokohama（铁牌题解）

A-FastForwarding

思路：

贪心就行了
0秒的时候 不能按键操作

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%dn", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lldn", n)
#define pldd(n,m) printf("%lld %lldn", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sc(n) scanf("%c",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x&-x)
#define pii map<int,int>
#define mk make_pair
#define rtl rt<<1
#define rtr rt<<1|1
#define int long long
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
inline int read()
{
int ret = 0, sgn = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
sgn = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
ret = ret*10 + ch - '0';
ch = getchar();
}
return ret*sgn;
}
inline void Out(int a){if(a>9) Out(a/10);putchar(a%10+'0');}
int qpow(int m, int k, int mod){int res=1,t=m;while(k){if(k&1)res=res*t%mod;t=t*t%mod;k>>=1;}return res;}
ll gcd(ll a,ll b){return b==0?a : gcd(b,a%b);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll inv(ll x,ll m){return qpow(x,m-2,m)%m;}
const int N = 5e6+10;
int n,m,q;
signed main()
{
signed t = 1;
//cin>>t;
while(t--)
{
cin>>n;
n -= 1;
int res = 1+n%3;
n -= n%3;
int tmp = 0;
int tt = 3;
while(tmp + tt*2 <= n)
{
tmp += tt*2;
tt *= 3;
res += 2;
}
int ttt = n-tmp;
while(ttt > 0 )
{
//cout<<ttt<<" "<<tt<<endl;
if(ttt >= tt)
{
res += ttt/tt;
ttt -= ttt/tt*tt;
}
tt /= 3;
if(tt == 1)
break;
}
cout<<res<<endl;
}
return 0;
}

B-Estimating the Flood Risk

思路：

BFS 从每个已知点出发，给所有点定一个高度（按bfs递减下去），如果某个已知点的高度的与搜索的高度违背则不可能。
否则 取该点可行的最大高度。

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%dn", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lldn", n)
#define pldd(n,m) printf("%lld %lldn", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sc(n) scanf("%c",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x&-x)
#define pii map<int,int>
#define mk make_pair
#define rtl rt<<1
#define rtr rt<<1|1
#define int long long
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
inline int read()
{
int ret = 0, sgn = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
sgn = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
ret = ret*10 + ch - '0';
ch = getchar();
}
return ret*sgn;
}
inline void Out(int a){if(a>9) Out(a/10);putchar(a%10+'0');}
int qpow(int m, int k, int mod){int res=1,t=m;while(k){if(k&1)res=res*t%mod;t=t*t%mod;k>>=1;}return res;}
ll gcd(ll a,ll b){return b==0?a : gcd(b,a%b);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll inv(ll x,ll m){return qpow(x,m-2,m)%m;}
const int N = 5e6+10;
int n,m,q;
int a[100][100];
int vis[100][100];
int mark[100][100];
int h[100][100];
int to[4][2] = {1,0,-1,0,0,1,0,-1};
int flag = 1;
int cnt = 0 ;
int valid(int x,int y)
{
return x>=0&&x<n&&y>=0&&y<m&&!vis[x][y];
}
struct node{
int x,y,h;
node(){}
node(int x_,int y_,int h_){x=x_;y=y_;h=h_;}
}nd[1005];
queue<node>
que;
void dfs(int xxx,int yyy,int hhh)
{
vis[xxx][yyy] = 1;
while(!que.empty())que.pop();
que.push(node(xxx,yyy,hhh));
while(!que.empty())
{
cnt ++;
node tmp = que.front();que.pop();
int x = tmp.x;int y = tmp.y;int hh = tmp.h;
if(mark[x][y] && hh > h[x][y])
{
flag = 0;
return;
}
a[x][y] = max(hh,a[x][y]);
for(int i
= 0 ; i < 4 ; i ++)
{
int xx = x+to[i][0];
int yy = y+to[i][1];
if(valid(xx,yy))
{
vis[xx][yy] = 1;
que.push(node(xx,yy,hh-1));
}
}
}
}
signed main()
{
signed t = 1;
//cin>>t;
while(t--)
{
cin>>n>>m>>q;
rep(i,0,n)
rep(j,0,m)
a[i][j] = -999999999;
for(int i = 0 ; i < q;
i ++)
{
int x,y;cin>>x>>y;
x-=1;
y-=1;
cin>>a[x][y];
mark[x][y] = 1;
h[x][y] = a[x][y];
}
rep(i,0,n-1)
rep(j,0,m-1)
{
if(mark[i][j] &&flag)
{
//cout<<i<<j<<endl;
dfs(i,j,a[i][j]);
memset(vis,0,sizeof(vis));
}
}
int res =0 ;
//cout<<cnt<<endl;
if(flag)
{
rep(i,0,n-1)
rep(j,0,m-1)
res += a[i][j];
cout<<res<<endl;
}
else
cout<<"No"<<endl;
}
return 0;
}

H-Parentheses Editor

思路：

cnt 记录当前第几个字符 碰到 ‘-’ 会回退
dp[cnt] 表示当前 连续匹配的类似()()的数量
match[cnt] 表示与当前括号匹配的左括号的id
那么每一次的ans 就是 ans += dp[cnt] 秒啊！
那么当碰到左括号时dp[cnt] = 0 ; match[cnt] = 0; st.push(cnt);
当碰到右括号时就可以进行转移了 dp[cnt] = dp[st.top-1]+1;

代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%dn", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lldn", n)
#define pldd(n,m) printf("%lld %lldn", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sc(n) scanf("%c",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x&-x)
#define pii map<int,int>
#define mk make_pair
#define rtl rt<<1
#define rtr rt<<1|1
#define int long long
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
inline int read()
{
int ret = 0, sgn = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
sgn = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
ret = ret*10 + ch - '0';
ch = getchar();
}
return ret*sgn;
}
inline void Out(int a){if(a>9) Out(a/10);putchar(a%10+'0');}
int qpow(int m, int k, int mod){int res=1,t=m;while(k){if(k&1)res=res*t%mod;t=t*t%mod;k>>=1;}return res;}
ll gcd(ll a,ll b){return b==0?a : gcd(b,a%b);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll inv(ll x,ll m){return qpow(x,m-2,m)%m;}
const int N = 2e6+10;
stack<int> st;
char s[N];
int dp[N];
int match[N];
signed main()
{
scanf("%s",s+1);
int len=strlen(s+1);
int cnt=0;
ll ans=0;
for(int i=1;i<=len;i++){
if(s[i]=='('){
cnt++;
dp[cnt]=0;
match[cnt]=0;
st.push(cnt);
}
else if(s[i]==')'){
cnt++;
if(!st.empty()){
match[cnt]=st.top();
dp[cnt]=dp[st.top()-1]+1;
st.pop();
}
else {
match[cnt]=0;
dp[cnt]=0;
}
ans+=dp[cnt];
}
else if(s[i]=='-'){
ans-=dp[cnt];
while(!st.empty()&&st.top()>=cnt)
st.pop();
// 这里是因为 如果当前cnt是和前面左括号匹配的话，那么之前这个左括号已经被弹出去了， 现在退回来了，那么还得把这个左括号给弄回来
if(match[cnt]!=0)
st.push(match[cnt]);
cnt--;
}
printf("%lldn",ans);
}
}

最后

以上就是细心向日葵为你收集整理的2019 ICPC Yokohama（铁牌题解）的全部内容，希望文章能够帮你解决2019 ICPC Yokohama（铁牌题解）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。