A
#include <bits/stdc++.h> using namespace std; typedef long long LL; map<string,char> ma; void init(){ ma["5--"] = 'E'; ma["2-"] = 'I'; ma["1-"] = 'E'; ma["4-"] = 'I'; ma["3-"] = 'E'; ma["6-"] = 'I'; ma["5-"] = 'E'; ma["7-"] = 'I'; ma["1"] = 'E'; ma["2"] = 'I'; ma["3"] = 'E'; ma["4"] = 'I'; ma["5"] = 'E'; ma["6"] = 'I'; ma["1+"] = 'E'; ma["7"] = 'I'; ma["3+"] = 'E'; ma["2+"] = 'I'; ma["5+"] = 'E'; ma["4+"] = 'I'; ma["1++"] = 'E'; ma["6+"] = 'I'; ma["3++"] = 'E'; ma["7+"] = 'I'; ma["0"] = 'X'; } int main() { init(); string str; LL n; scanf("%I64d",&n); for( LL i = 1;i <= n;i++ ){ cin >> str; cout << ma[str]; } return 0; }B
C.简单贪心
#include <cstdio> #include<vector> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; LL n,k,c,x,d; typedef pair<LL,LL> pii; vector<pii> ve; int main() { scanf("%I64d%I64d%I64d",&n,&k,&c); LL ans= 0; for( LL i = 1;i <= n;i++ ){ scanf("%I64d%I64d",&d,&x); ans += (d-1) / k * x; ve.push_back( pii( x,(d-1)/k ) ); } sort( ve.begin(),ve.end(),greater<pii>() ); for( LL i = 0;i< ve.size();i++ ){ LL x = ve[i].first,y = ve[i].second; if( !y ) continue; LL cnt = min(c,y); ans -= cnt * x; c -= cnt; if( !c ) break; } printf("%I64d\n",ans); return 0; }D
E。容易看出两个栈就可以完成这个操作，问题转化为什么情况下一个栈就可以完成这个操作。这个栈一定是这种形式的
321546879.......然而这种局部有序的形式不好判断，我们直接来用一个栈来进行模拟操作吧。
include <cstdio> #include<stack> using namespace std; typedef long long LL; const LL maxn = 100000 + 10; LL a[maxn]; stack<LL> st; int main() { LL n,T,pre,x; scanf("%I64d",&T); while( T-- ){ LL b = 1,cnt = 0; scanf("%I64d",&n); for( LL i = 1;i <= n;i++ ){ scanf("%I64d",&a[i]); } LL cur = 1; while( st.size() ) st.pop(); for( LL i = 1;i <= n;i++ ){ st.push( a[i] ); while( st.size() && st.top() == cur ){ cur++; st.pop(); } } if( st.size() ) printf("2\n"); else printf("1\n"); } return 0; }F.dp[ i ] 代表 i*i 的正方形可以放多少种，dp2[ i ]代表 i * (i-1)的矩形可以放多少种，然后就递推式自己瞎搞搞就出来了。
这题其实可以直接推公式，大概思路就是一个矩形中，算出有多少个边长为k的正方形，统计每个边长为K的正方形中，恰好四个顶点都在矩形边上的正方形有多少个。这样也可以做到不重不漏。
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL dp[100000 + 10],dp2[100000 + 10]; int main() { dp[1] = 1; dp[2] = 6; LL T,n,m; dp2[1] = 0; dp2[2] = 2; for( LL i = 3;i <= 1e5;i++ ){ dp2[i] = 2*dp[i-1] - dp2[i-1]; dp[i] = 4 * dp[i-1] - 4 * dp2[i-1] + dp[i-2] + i; } scanf("%I64d",&T); while( T-- ){ scanf("%I64d%I64d",&n,&m); if( n > m ) swap( n,m ); if( n == m ){ printf("%I64d\n",dp[n]); continue; } LL re = (m-n+1) * dp[n] - ( m-n ) * dp2[n]; printf("%I64d\n",re); } return 0; }J。重点就是发现长度为n的算式的加和只与开头的数字有关。这题如果没发现这个结论直接做的话dp是超时的，以后长个心眼吧。。。。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn= 5e5+10; const LL mod= 998244353 ; LL mpow[maxn],dp[maxn],s[maxn]; int main() { LL n; mpow[0] = 1; for( LL i = 1;i <= 5e5;i++ ){ mpow[i] = mpow[i-1]*10 % mod; } s[0] = 0; for( LL i = 1;i <= 5e5;i++ ){ s[i] = (mpow[i]*(mpow[i]-1)/2)%mod; } dp[0] = 0; dp[1] = 10; for( LL i = 2;i <= 5e5;i++ ){ dp[i] = (10 * dp[i-1] % mod + 20 * dp[i-2] % mod) % mod; } LL T; scanf("%I64d",&T); while( T-- ){ scanf("%I64d",&n); LL ans = s[n]; for( LL i = 1;i < n-1;i++ ){ ans = (ans + (2*s[i] * dp[ n - (i+1) ])%mod ) % mod; } printf("%I64d\n",ans); } return 0; }K
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 1000; const LL mod = 998244353; LL a[maxn]; int main() { LL n,k; scanf("%I64d%I64d",&n,&k); for( LL i = n;i >= 0;i-- ){ scanf("%I64d",&a[i]); } a[n+1] = 0; for( LL i = 1;i <= k;i++ ){ for( LL j = 0;j <= n;j++ ){ a[j] = (a[j+1] * (1+j) ) % mod; } } for( LL i =n;i >= 0;i-- ){ printf("%I64d ",a[i]); } return 0; }
