Codeforces Round #739 (Div. 3)（编辑距离+数位dp）

本是古典何须时尚 2022-09-06 00:21 140阅读 0赞

## a ##

int n;
    int arr[N];
     
    void solve()
    { 
    	cin >> n;
    	cout << arr[n] << endl;
    }
     
    int main()
    { 
     
    	ios::sync_with_stdio(false);cin.tie(0);
    	int x = 1;
    	rep(i,1,100000)
    	{ 
    		if(i%3==0 || i%10==3) continue;
    		else arr[x++]=i;
    	}
    	int Case;cin >> Case;
    	while(Case--)
    		solve();
    	return 0;
    }

--------------------

## b ##

找规律就行，

// Problem: B. Who's Opposite?
    // Contest: Codeforces - Codeforces Round #739 (Div. 3)
    // URL: https://codeforces.com/contest/1560/problem/B
    // Memory Limit: 256 MB
    // Time Limit: 1000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    using namespace std;
    
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    const int N=1e5+100;
    int n;
    int arr[N];
    
    void solve()
    { 
    	int a, b, c;
    	cin >> a >> b >> c;
    	int cc = abs(a-b);
    	int ans = - 1;
    	if(c - cc > 0) ans = c - cc;
    	if(c + cc <= 2*cc) ans = c + cc;
    	if(c > 2*cc) 
    	{ 
    		cout << -1 << endl;
    		return ;
    	}
    	if(cc < min(a,b))  // 注意这里是小于
    	{ 
    		cout << -1 << endl;
    		return ;
    	}
    	cout << ans << endl;
    }
    
    int main()
    { 
    
    	ios::sync_with_stdio(false);cin.tie(0);
    	int Case;cin >> Case;
    	while(Case--)
    		solve();
    	return 0;
    }

--------------------

## c ##

// Problem: C. Infinity Table
    // Contest: Codeforces - Codeforces Round #739 (Div. 3)
    // URL: https://codeforces.com/contest/1560/problem/C
    // Memory Limit: 256 MB
    // Time Limit: 1000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    using namespace std;
    #define lowbit(x) (x&-x)
    #define pf(a) printf("%d\n",a)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define dbg(x) cout << #x << " = " << x << endl
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    #define fep(i,a,b) for(int i=b;i>=a;--i)
    typedef long long ll;
    typedef unsigned long long ull;
    
    const int inf=0x3f3f3f3f;
    const int N=1e5+100;
    int n;
    int arr[N];
    
    void solve()
    { 
    	ll k;
    	cin >> k;
    	ll cc = 0, r = 0;
    	ll c;
    	if(k==1) 
    	{ 
    		cout << 1 << " " << 1 << endl;
    		return ;
    	}
    	for(int i=1;i<=N;i++)
    	{ 
    		if(i*i <= k && k <= (i+1)*(i+1))
    		{ 
    			c=i+1;
    			break;
    		}
    	}
    	if( k >= c*c-c+1) 
    	{ 
    		cc = c;
    		r = c*c - k + 1;
    	}
    	else { 
    		r = c;
    		cc = c - (c*c-c+1 - k);
    	}
    	
    	cout << cc << " " << r << endl;
    }
    
    int main()
    { 
    
    	ios::sync_with_stdio(false);cin.tie(0);
    	int Case;cin >> Case;
    	while(Case--)
    		solve();
    	return 0;
    }

--------------------

## d字符串匹配 ##

// Problem: D. Make a Power of Two
    // Contest: Codeforces - Codeforces Round #739 (Div. 3)
    // URL: https://codeforces.com/contest/1560/problem/D#
    // Memory Limit: 256 MB
    // Time Limit: 1000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    using namespace std;
    #define lowbit(x) (x&-x)
    #define pf(a) printf("%d\n",a)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define dbg(x) cout << #x << " = " << x << endl
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    #define fep(i,a,b) for(int i=b;i>=a;--i)
    #define ll long long
    ll str[50];
    
    
    ll pow_mod(ll a, ll k)
    { 
        ll ans = 1;
        while(k)
        { 
            if(k % 2)
                ans *= a;
            a *= a;
            k /= 2;
        }
        return ans;
    }
    
    int calc(string a, string b) 
    { 
        int n = a.size();
        int m = b.size();
        int i = 0, j = 0;
        int ret = 0;
        while(true) { 
            while(i < n && a[i] != b[j]) i++;
            if(i == n) break;
            if(a[i] == b[j]) { 
                ret++;
                i++;
                j++;
            }
            if(j == m) break;
        }
        return m + n - 2 * ret;
     
    }
    void solve()
    { 
    	int n;
    	cin >> n;
    	
    	int ans = 500;
    	
    	rep(i,0,60)
    		ans = min(ans, calc(to_string(n),to_string(str[i])));
    
    	cout << ans << endl;
    }
    
    int main()
    { 
    	for(ll i = 0; i <= 60; i++)
    		str[i] = pow_mod((ll)2,i);
    	
    	int Case;cin >> Case;
    	while(Case--)
    		solve();
    	return 0;
    }