A:

Solved.

分别处理出每个%7后余数的数字个数,再组合一下

 #include <bits/stdc++.h>
using namespace std; #define ll long long
int n, m;
ll cnt[][]; ll calc(ll x, ll y)
{
if (x % >= y) return x / + ;
return x / ;
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
memset(cnt, , sizeof cnt);
for (int i = ; i < ; ++i)
{
cnt[][i] += calc(n, i);
cnt[][i] += calc(m, i);
}
ll res = ;
--cnt[][], --cnt[][];
cnt[][] = cnt[][];
for (int i = ; i < ; ++i)
res += cnt[][i] * cnt[][ - i];
printf("%lld\n", res);
}
return ;
}

B:

Solved.

状压DP.

 #include <bits/stdc++.h>
using namespace std; #define ll long long
int n,m;
ll f[][<<];
bool ins[<<];
int main(){
while(cin>>n>>m&&n){
for(int i=;i<(<<m);i++){
bool cnt=,hasodd=;
for(int j=;j<m;j++)
if((i>>j)&)hasodd|=cnt,cnt=;
else cnt^=;
ins[i]=hasodd|cnt?:; }
f[][]=;
for(int i=;i<=n;i++)
for(int j=;j<(<<m);j++){
f[i][j]=;
for(int k=;k<(<<m);k++){
if((j&k)==&&ins[j|k])
f[i][j]+=f[i-][k];
} }
cout<<f[n][]<<endl;
}
}

C:

Solved.

 #include<bits/stdc++.h>

 using namespace std;

 int n, s;

 int main()
{
while(~scanf("%d %d", &n, &s))
{
int Min = 0x3f3f3f3f;
for(int i = ; i < n; ++i)
{
int num = ;
scanf("%d" , &num);
Min = min(Min, num);
}
printf("%d\n", s * Min);
}
return ;
}

D:

Solved.

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;
int n, s;
int arr[maxn]; int main()
{
while(~scanf("%d %d", &n, &s))
{
for(int i = ; i <= n; ++i)
{
scanf("%d", arr + i);
}
sort(arr + , arr + + n);
printf("%d\n", arr[n - ] * s);
}
return ;
}

E:

Solved.

最长公共子序列。

 #include<bits/stdc++.h>
using namespace std;
const int maxn=;
int f[maxn][maxn];
char s1[maxn],s2[maxn];
int main(){
cin>>s1+>>s2+;
int n=strlen(s1+),m=strlen(s2+);
for(int i=;i<=n;i++)
{ for(int j=;j<=m;j++)
{
f[i][j]=max(f[i - ][j], f[i][j - ]);
if(s1[i]==s2[j])
{
f[i][j]=max(f[i][j],f[i-][j-] + );
} }
}
printf("%d\n",f[n][m]);
}

F:

Solved.

$dp[i][j][k] 表示到达i, j 的时候步数为k的方案数$

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
const ll MOD = 1e9 + ;
ll dp[maxn][maxn][maxn];
int fx[][]={{,},{,-},{-,},{-,-},{,},{,-},{-,},{-,-}};
int n,m,s;
inline bool check(int x,int y){
if(x< || x>n || y< ||y>m)return false;
return true;
}
int main(){
while(cin>>n>>m>>s)
{
memset(dp, , sizeof dp);
dp[][][]=;
for(int k=;k<=s;k++)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++){
for(int t=;t<;t++)
{
int x=i+fx[t][];
int y=j+fx[t][];
if(check(x,y)){
dp[i][j][k]+=dp[x][y][k-];
dp[i][j][k]%=MOD;
}
}
}
}
}
cout<<dp[n][m][s]<<endl;
}
}

G:

Unsolved.

H:

Solved.

考虑离线,对$每个数处理出到L左边离它最近的非互质的数,以及到R右边$离它最近的非互质的数,

再考虑先固定$l, 对每一个r处理出答案$

再考虑什么时候把数的贡献加进去,仅当这个数的$L < l 的时候便可以加入贡献,贡献的范围是[pos, R - 1], pos 表示那个数的位置$

 #include <bits/stdc++.h>
using namespace std; #define N 100010
#define pii pair <int, int>
int n, q, a[N], l[N], r[N], dp[N], ans[N], vis[N];
vector <int> fac[N];
vector <pii> v[N], qv[N]; namespace SEG
{
int a[N << ], lazy[N << ];
void build(int id, int l, int r)
{
a[id] = ;
if (l == r) return;
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
}
void pushdown(int id, int l, int r, int mid)
{
if (!lazy[id]) return;
lazy[id << ] += lazy[id];
a[id << ] += lazy[id] * (mid - l + );
lazy[id << | ] += lazy[id];
a[id << | ] += lazy[id] * (r - mid);
lazy[id] = ;
}
void pushup(int id) { a[id] = a[id << ] + a[id << | ]; }
void update(int id, int l, int r, int ql, int qr, int val)
{
if (l >= ql && r <= qr)
{
a[id] += val * (r - l + );
lazy[id] += val;
return;
}
int mid = (l + r) >> ;
pushdown(id, l, r, mid);
if (ql <= mid) update(id << , l, mid, ql, qr, val);
if (qr > mid) update(id << | , mid + , r, ql, qr, val);
pushup(id);
}
int query(int id, int l, int r, int pos)
{
if (l == r) return a[id];
int mid = (l + r) >> ;
pushdown(id, l, r, mid);
if (pos <= mid) return query(id << , l, mid, pos);
else return query(id << | , mid + , r, pos);
}
} void init()
{
for (int i = ; i <= ; ++i)
{
if (vis[i]) continue;
fac[i].push_back(i);
for (int j = * i; j <= ; j += i)
{
vis[j] = ;
fac[j].push_back(i);
}
}
} int main()
{
init();
while (scanf("%d%d", &n, &q) != EOF)
{
for (int i = ; i <= n + ; ++i) l[i] = , r[i] = n + , v[i].clear(), qv[i].clear();
for (int i = ; i <= n; ++i) scanf("%d", a + i);
memset(vis, , sizeof vis);
for (int i = ; i <= n; ++i)
for (auto it : fac[a[i]])
l[i] = max(l[i], vis[it]), vis[it] = i;
memset(vis, 0x3f, sizeof vis);
for (int i = n; i >= ; --i)
for (auto it : fac[a[i]])
r[i] = min(r[i], vis[it]), vis[it] = i;
//for (int i = 1; i <= n; ++i) printf("%d %d\n", l[i], r[i]);
//for (int i = 1; i <= n; ++i) for (int j = 0, len = fac[a[i]].size(); j < len; ++j) printf("%d%c", fac[a[i]][j], " \n"[j == len - 1]);
for (int i = ; i <= n; ++i)
v[l[i]].emplace_back(r[i], i);
for (int qq = , l, r; qq <= q; ++qq)
{
scanf("%d%d", &l, &r);
qv[l].emplace_back(r, qq);
}
SEG::build(, , n);
for (int i = ; i <= n; ++i)
{
for (auto it : v[i - ])
SEG::update(, , n, it.second, it.first - , );
for (auto it : qv[i])
ans[it.second] = SEG::query(, , n, it.first);
SEG::update(, , n, i, r[i] - , -);
}
for (int i = ; i <= q; ++i) printf("%d\n", ans[i]);
}
return ;
}

I:

Solved.

特判$n == 0 并且 m == 0 的情况$

其他情况下,因为$k >= |n - m| 先手的人只需要去掉石子使得两堆相同,然后跟着另一个人取就可以必胜$

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll n, m, k;

 int main()
{
while(~scanf("%lld %lld %lld", &n, &m, &k))
{
if(n == || m == ) puts("LAOZI CHUI SI NI!");
else puts("HAI YOU SEI!");
}
return ;
}

J:

Solved.

考虑 末尾两位为00, 25, 50, 75四种状态

 #include<bits/stdc++.h>

 using namespace std;

 const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + ; char str[maxn]; int main()
{
while(~scanf("%s", str + ))
{
int ans = INF;
int len = strlen(str + ); //
int tmp1 = -, tmp2 = -;
for(int i = len; i >= ; --i)
{
if(str[i] == '')
{
if(tmp1 == -) tmp1 = len - i;
else if(tmp2 == -)
{
tmp2 = len - i - ;
break;
}
}
}
if(tmp1 != - && tmp2 != -) ans = min(ans, tmp1 + tmp2); //
tmp1 = -, tmp2 = -;
for(int i = len; i >= ; --i)
{
if(str[i] == '')
{
if(tmp1 == -) tmp1 = len - i;
}
if(str[i] == '')
{
if(tmp2 == -) tmp2 = len - i;
}
} if(tmp1 != - && tmp2 != -)
{
if(tmp1 < tmp2)
{
ans = min(ans, tmp1 + tmp2 - );
}
else
{
ans = min(ans, tmp1 + tmp2);
}
} //
tmp1 = -, tmp2 = -;
for(int i = len; i >= ; --i)
{
if(str[i] == '')
{
if(tmp1 == -) tmp1 = len - i;
}
if(str[i] == '')
{
if(tmp2 == -) tmp2 = len - i;
}
} if(tmp1 != - && tmp2 != -)
{
if(tmp1 < tmp2)
{
ans = min(ans, tmp1 + tmp2 - );
}
else
{
ans = min(ans, tmp1 + tmp2);
}
}
//
tmp1 = -, tmp2 = -;
for(int i = len; i >= ; --i)
{
if(str[i] == '')
{
if(tmp1 == -) tmp1 = len - i;
}
if(str[i] == '')
{
if(tmp2 == -) tmp2 = len - i;
}
}
if(tmp1 != - && tmp2 != -)
{
if(tmp1 < tmp2)
{
ans = min(ans, tmp1 + tmp2 - );
}
else
{
ans = min(ans, tmp1 + tmp2);
}
}
if(ans == INF) ans = -;
printf("%d\n", ans);
}
return ;
}
05-11 16:58
查看更多